title: Kart: a divide-and-conquer algorithm for NGS read alignment.
abstract: BACKGROUND
  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 tolerate much higher error rates. The experiments show that Kart spends much less time on longer reads than other aligners and still produce reliable alignments even when the error rate is as high as 15%.
  
  
  METHODS
  Kart is available at https://github.com/hsinnan75/Kart/ .
  
  
  BACKGROUND
  hsu@iis.sinica.edu.tw.
  
  
  BACKGROUND
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Institute of Information Science, Academia Sinica, Taipei, Taiwan.
authors.forename: Hsin-Nan
authors.initials: HN
authors.lastname: Lin
authors.affiliation: Institute of Information Science, Academia Sinica, Taipei, Taiwan.
authors.forename: Wen-Lian
authors.initials: WL
authors.lastname: Hsu
mesh_terms: D000465:Algorithms; D014644:Genetic Variation; D015894:Genome, Human; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods; D012984:Software