Answers.Body: <p>The following javascript does what you want. You need node.js to run it. It should be easy to translate the code to Python. I have not carefully tested it. Use with caution.</p>
  
  <p>EDIT (response to new comments): the program has been changed to compute the sum of lengths. Note that only a tandem repeat of length k*2 or longer is counted. For example in sequence <code>ATTGGGATTGGGATTcGGGATTGGG</code>, the script returns 15, because the second is not long enough. Counting length smaller than k*2 will be slower and more complex, but is often not the right thing to do. For example, in <code>ATTGGGATTGGGcccccccgaaatcgatagcatcgaGGGATTGcgatc</code>, we would not count the second <code>GGGATTG</code> as a tandem repeat.</p>
  
  <p>On performance, for an input string of length $l$, the time complexity of this script is $O(l)$ associated with a small constant. It will be efficient and adequate to practical uses.</p>
  
  <p>If you use <a href="https://tandem.bu.edu/trf/trf.html" rel="noreferrer">TRF</a>, you should run it on your sequences and then test if any tandem repeats it finds match <code>GGGAAT</code> – the procedure will be similar to my script, except that TRF will also find impure repeats.</p>
  
  <pre class="lang-js prettyprint-override"><code>// given the repeat unit length _k_, find all tandem repeats of 2*k or longer
  function trf_k(k, str)
  {
      var streak = 0, a = [];
      for (var i = k; i &lt;= str.length; ++i) {
          if (i &lt; str.length &amp;&amp; str[i] == str[i - k]) {
              ++streak;
          } else {
              if (streak &gt;= k)
                  a.push([i - streak - k, i]);
              streak = 0;
          }
      }
      return a;
  }
  // find the sum of tandem repeat length with _kmer_ being the repeat unit
  function trf_kmer(kmer, str)
  {
      var a = trf_k(kmer.length, str), sum = 0;
      for (var i = 0; i &lt; a.length; ++i)
          if (str.substring(a[i][0], a[i][1]).indexOf(kmer) &gt;= 0)
              sum += a[i][1] - a[i][0];
      return sum;
  }
  
  var str = 'xATTGGGATTGGGATTGxGATTGGGATTGGGATTGGGATTGxx';
  console.log(trf_kmer('GGGATT', str));
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-15T10:00:56.983Z
Answers.Text: Sorry i mean that i want the perfect match of each possible repeated sequences, and in the case of your algorithm, when there is a gap it's still count the kmer. Indeed the task is highly customized. I guess I'll just start using parallelism on my program. I'll take a look into TRF, thanks.
Answers.UserDisplayName: hilta007
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-15T15:13:13.040Z
Answers.Text: @hilta007 Thanks for the explanation (I am deleting my old comment BTW). If you want to find the total length, just change "max" to "sum", but with a caveat (see edits for detail). My implementation should be fairly efficient. I wouldn't worry too much about performance. A good single-threaded script can sometimes be faster than a bad multi-threaded C/C++ program.
Answers.UserDisplayName: user172818
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-15T16:10:31.620Z
Answers.Text: Thanks for the edits, waiting the results of TRF and my own algorithm to compare quality/speed for now. I'll keep your algorithm in mind.
Answers.UserDisplayName: hilta007
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2018-03-14T15:03:22.837Z
Answers.LastActivityDate: 2018-03-15T15:08:19.987Z
Answers.LastEditDate: 2018-03-15T15:08:19.987Z
Answers.UserDisplayName: user172818
Body: <p>Working on a fastQ file, I would like to get the occurrences of repeated sequences for all possible kmers of a given length that cover at least 90% of the read's length for the whole data set.</p>
  
  <p>example : </p>
  
  <blockquote>
    <p>for a length 6 with the kmer "ATTGGG" and a data set  containing reads of 300 bases each</p>
  </blockquote>
  
  <p>I want to obtain the occurrences of the following kmers :</p>
  
  <pre><code>ATTGGGATTGGGATTGGGATTGGGATTGGGATTGGG......  (90 % of the read's length without  gaps) 
  ATTGGGATTGGGATTGGGATTGGGATTGGGATTGGGA.....  (91%)
  ATTGGGATTGGGATTGGGATTGGGATTGGGATTGGGAT....  (92%)
  </code></pre>
  
  <p>this for all possible combinations of kmers of length = 6.</p>
  
  <p>I have done some research and tested many softwares such as (KMC2,Jellyfish,Khmer,Dsk,Scturtle) but none matched what I would like to do, because I want to obtain the occurrences of the repeated kmer without any possible gaps in-between with a certain % of read coverage.</p>
  
  <p>I've done a naive algorithm that works but the optimization isn't the best obviously. Is there a tool that does the trick ?</p>
  
Tags: <fastq><k-mer><reads><repeat-elements>
Title: Counting repeated kmers sequences that match at least x % of reads sequence
ThreadText: # Counting repeated kmers sequences that match at least x % of reads sequence
  
  (Asked by: username_0 on 2018-03-14)
  
  Working on a fastQ file, I would like to get the occurrences of repeated sequences for all possible kmers of a given length that cover at least 90% of the read's length for the whole data set.
  
  example :
  
  > for a length 6 with the kmer "ATTGGG" and a data set containing reads of 300 bases each
  
  I want to obtain the occurrences of the following kmers :
  
  ```
  ATTGGGATTGGGATTGGGATTGGGATTGGGATTGGG......  (90 % of the read's length without  gaps) 
  ATTGGGATTGGGATTGGGATTGGGATTGGGATTGGGA.....  (91%)
  ATTGGGATTGGGATTGGGATTGGGATTGGGATTGGGAT....  (92%)
  
  ```
  
  this for all possible combinations of kmers of length = 6.
  
  I have done some research and tested many softwares such as (KMC2,Jellyfish,Khmer,Dsk,Scturtle) but none matched what I would like to do, because I want to obtain the occurrences of the repeated kmer without any possible gaps in-between with a certain % of read coverage.
  
  I've done a naive algorithm that works but the optimization isn't the best obviously. Is there a tool that does the trick ?
  
  **Tags:** fastq, k-mer, reads, repeat-elements
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2018-03-14. Score: 6
  
  The following javascript does what you want. You need node.js to run it. It should be easy to translate the code to Python. I have not carefully tested it. Use with caution.
  
  EDIT (response to new comments): the program has been changed to compute the sum of lengths. Note that only a tandem repeat of length k\*2 or longer is counted. For example in sequence `ATTGGGATTGGGATTcGGGATTGGG`, the script returns 15, because the second is not long enough. Counting length smaller than k\*2 will be slower and more complex, but is often not the right thing to do. For example, in `ATTGGGATTGGGcccccccgaaatcgatagcatcgaGGGATTGcgatc`, we would not count the second `GGGATTG` as a tandem repeat.
  
  On performance, for an input string of length $l$, the time complexity of this script is $O(l)$ associated with a small constant. It will be efficient and adequate to practical uses.
  
  If you use [TRF](https://tandem.bu.edu/trf/trf.html), you should run it on your sequences and then test if any tandem repeats it finds match `GGGAAT` – the procedure will be similar to my script, except that TRF will also find impure repeats.
  
  ```js
  // given the repeat unit length _k_, find all tandem repeats of 2*k or longer
  function trf_k(k, str)
  {
      var streak = 0, a = [];
      for (var i = k; i <= str.length; ++i) {
          if (i < str.length && str[i] == str[i - k]) {
              ++streak;
          } else {
              if (streak >= k)
                  a.push([i - streak - k, i]);
              streak = 0;
          }
      }
      return a;
  }
  // find the sum of tandem repeat length with _kmer_ being the repeat unit
  function trf_kmer(kmer, str)
  {
      var a = trf_k(kmer.length, str), sum = 0;
      for (var i = 0; i < a.length; ++i)
          if (str.substring(a[i][0], a[i][1]).indexOf(kmer) >= 0)
              sum += a[i][1] - a[i][0];
      return sum;
  }
  
  var str = 'xATTGGGATTGGGATTGxGATTGGGATTGGGATTGGGATTGxx';
  console.log(trf_kmer('GGGATT', str));
  
  ```
  
  > **Comments:**
  > **username_0**: Sorry i mean that i want the perfect match of each possible repeated sequences, and in the case of your algorithm, when there is a gap it's still count the kmer. Indeed the task is highly customized. I guess I'll just start using parallelism on my program. I'll take a look into TRF, thanks.  
  > **username_1**: @username_0 Thanks for the explanation (I am deleting my old comment BTW). If you want to find the total length, just change "max" to "sum", but with a caveat (see edits for detail). My implementation should be fairly efficient. I wouldn't worry too much about performance. A good single-threaded script can sometimes be faster than a bad multi-threaded C/C++ program.  
  > **username_0**: Thanks for the edits, waiting the results of TRF and my own algorithm to compare quality/speed for now. I'll keep your algorithm in mind.  
  
  ---
  
  