DIVIDE-AND-CONQUER GLOBAL ALIGNMENT ALGORITHM FOR FINDING HIGHLY SIMILAR CANDIDATES OF A SEQUENCE IN DATABASE

摘要

A divide-and-conquer global alignment algorithm for finding highly similar candidates of a sequence in database is disclosed. The invention gives a divide-and-conquer algorithm called Kart, that separates the given sequence into smaller pieces whose alignment can be carried out independently, and their concatenated alignment constitutes the global alignment of the entire sequence. Kart could be viewed as aligning multiple seeds simultaneously in parallel. We illustrate the idea using the read mapping of Next-generation sequencing (NGS) as an example. NGS provides a great opportunity to investigate genome-wide variation at nucleotide resolution. Due to the huge amount of data, NGS applications require very fast alignment algorithms. The invention can process long reads as fast as short reads. Furthermore, it can tolerate much higher error rates. The experiments show that Kart spends much less time on longer reads than most aligners and still produce reliable alignments.