An exhaustive genome assembly algorithm using k-mers to indirectly perform N-squared comparisons in O(N)

We present an algorithm that indirectly makes N² sequence comparisons in O(N) with respect to the size of the genome. This algorithm is very applicable in assembling whole genomes from the thousands of DNA sequence fragments that are generated in shotgun sequencing. First, we assume that fragments that share k-mers should overlap in the final assembly. We then catalog all k-mers that exist in the shotgun library and infer links between fragments that share k-mers. These links are then used to represent edges in a graph. This graph is generated in O(N) yet represents the result of comparing every fragment to every other fragment.