title: Increase string overlap matrix building efficiency
body: <p>I have a huge list (N = ~1million) of strings 100 characters long that I'm trying to find the overlaps between. For instance, one string might be</p>
  <pre><code>XXXXXXXXXXXXXXXXXXAACTGCXAACTGGAAXA (and so on)
  </code></pre>
  <p>I need to build an N by N matrix that contains the longest overlap value for every string with every other string. My current method is (pseudocode)</p>
  <blockquote>
  <p>read in all strings to array</p>
  <p>create empty NxN matrix</p>
  <p>compare each string to every string with a higher array index (to avoid redoing comparisons)</p>
  <p>Write longest overlap to matrix</p>
  </blockquote>
  <p>There's a lot of other stuff going on, but I really need a much more efficient way to build the matrix. Even with the most powerful computing clusters I can get my hands on this method takes days.</p>
  <p>In case you didn't guess, these are DNA fragments. X indicates &quot;wild card&quot; (probe gave below a threshold quality score) and all other options are a base (A, C, T, or G). I tried to write a quaternary tree algorithm, but this method was far too memory intensive.</p>
  <p>I'd love any suggestions you can give for a more efficient method; I'm working in C++ but pseudocode/ideas or other language code would also be very helpful.</p>
  <p><strong>Edit:</strong> some code excerpts that illustrate my current method. Anything not particularly relevant to the concept has been removed</p>
  <pre><code>//part that compares them all to each other
  for (int j=0; j&lt;counter; j++) //counter holds # of DNA
      for (int k=j+1; k&lt;counter; k++)
          int test = determineBestOverlap(DNArray[j],DNArray[k]);
  
  //boring stuff
  
  //part that compares strings. Definitely very inefficient,
  //although I think the sheer number of comparisons is the main problem
  int determineBestOverlap(string str1, string str2)
  {
      int maxCounter = 0, bestOffset = 0;
      //basically just tries overlapping the strings every possible way
      for (int j=0; j&lt;str2.length(); j++)
      {
          int counter = 0, offset = 0;
          while (str1[offset] == str2[j+offset] &amp;&amp; str1[offset] != 'X') 
          {
                counter++;
                offset++;
          }
          
          if (counter &gt; maxCounter)
          {
                      maxCounter = counter;
                      bestOffset = j;
          }
      }
      return maxCounter; 
  } //this simplified version doesn't account for flipped strings
  </code></pre>