Kart: a divide-and-conquer algorithm for NGS read alignment.

Area of Science:

• Genomics
• Bioinformatics
• Computational Biology

Background:

• Next-generation sequencing (NGS) generates vast amounts of data, necessitating rapid and precise alignment algorithms.
• Existing read mapping tools often struggle with longer reads due to their sequential nature.

Purpose of the Study:

• To develop a novel algorithm for efficient and accurate read mapping of next-generation sequencing data.
• To address the computational challenges posed by long reads in genome-wide variation analysis.

Main Methods:

• Developed a divide-and-conquer algorithm named Kart.
• Implemented a strategy to divide long reads into smaller, independently alignable fragments.

Main Results:

• Kart processes long reads as quickly as short reads.
• The algorithm effectively handles fragments requiring gapped alignment (average 20 bp).
• Kart demonstrates high accuracy even with error rates up to 15% and significantly outperforms other aligners on longer reads.

Conclusions:

• Kart offers a significant advancement in read mapping speed and accuracy for NGS data.
• The algorithm's ability to handle long reads and high error rates facilitates more comprehensive genome-wide variation studies.