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

ABSTRACT:

Motivation

Next-generation sequencing (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 and accurate alignment algorithms. Most existing algorithms for read mapping basically adopt seed-and-extend strategy, which is sequential in nature and takes much longer time on longer reads.

Results

We develop a divide-and-conquer algorithm, called Kart, which can process long reads as fast as short reads by dividing a read into small fragments that can be aligned independently. Our experiment result indicates that the average size of fragments requiring the more time-consuming gapped alignment is around 20 bp regardless of the original read length. Furthermore, it can tole

SUBMITTER: Lin HN 

PROVIDER: S-EPMC5860120 | biostudies-literature | 2017 Aug

REPOSITORIES: biostudies-literature