{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T04:28:45Z","timestamp":1774672125547,"version":"3.50.1"},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"15","license":[{"start":{"date-parts":[[2017,4,4]],"date-time":"2017-04-04T00:00:00Z","timestamp":1491264000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017,8,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>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.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>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\u2009bp 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%.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and Implementation<\/jats:title>\n                  <jats:p>Kart is available at https:\/\/github.com\/hsinnan75\/Kart\/.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Supplementary information<\/jats:title>\n                  <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btx189","type":"journal-article","created":{"date-parts":[[2017,3,31]],"date-time":"2017-03-31T20:29:55Z","timestamp":1490992195000},"page":"2281-2287","source":"Crossref","is-referenced-by-count":42,"title":["Kart: a divide-and-conquer algorithm for NGS read alignment"],"prefix":"10.1093","volume":"33","author":[{"given":"Hsin-Nan","family":"Lin","sequence":"first","affiliation":[{"name":"Institute of Information Science, Academia Sinica, Taipei, Taiwan"}]},{"given":"Wen-Lian","family":"Hsu","sequence":"additional","affiliation":[{"name":"Institute of Information Science, Academia Sinica, Taipei, Taiwan"}]}],"member":"286","published-online":{"date-parts":[[2017,4,4]]},"reference":[{"key":"2023063012495568000_btx189-B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol"},{"key":"2023063012495568000_btx189-B2","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2105-13-238","article-title":"Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory","volume":"13","author":"Chaisson","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023063012495568000_btx189-B3","doi-asserted-by":"crossref","DOI":"10.1093\/nar\/gkq010","article-title":"Incorporating sequence quality data into alignment improves DNA read mapping","volume":"38","author":"Frith","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2023063012495568000_btx189-B4","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pcbi.1000502","article-title":"Fast mapping of short sequences with mismatches, insertions and deletions using index structures","volume":"5","author":"Hoffmann","year":"2009","journal-title":"Plos Comput. Biol"},{"key":"2023063012495568000_btx189-B5","doi-asserted-by":"crossref","first-page":"A95","DOI":"10.1371\/journal.pone.0007767","article-title":"BFAST: an alignment tool for large scale genome resequencing","volume":"4","author":"Homer","year":"2009","journal-title":"Plos One"},{"key":"2023063012495568000_btx189-B6","doi-asserted-by":"crossref","first-page":"2395","DOI":"10.1093\/bioinformatics\/btn429","article-title":"SeqMap: mapping massive amount of oligonucleotides to the genome","volume":"24","author":"Jiang","year":"2008","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B7","first-page":"656","article-title":"BLAT\u2013the BLAST-like alignment tool","volume":"12","author":"Kent","year":"2002","journal-title":"Genome Res"},{"key":"2023063012495568000_btx189-B8","doi-asserted-by":"crossref","first-page":"357. U121","DOI":"10.1038\/nmeth.3317","article-title":"HISAT: a fast spliced aligner with low memory requirements","volume":"12","author":"Kim","year":"2015","journal-title":"Nat. Methods"},{"key":"2023063012495568000_btx189-B9","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with Bowtie 2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat. Methods"},{"key":"2023063012495568000_btx189-B10","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead","year":"2009","journal-title":"Genome Biol"},{"key":"2023063012495568000_btx189-B11","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1093\/bioinformatics\/btw152","article-title":"Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences","volume":"32","author":"Li","year":"2016","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B12","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B13","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","article-title":"Fast and accurate long-read alignment with Burrows-Wheeler transform","volume":"26","author":"Li","year":"2010","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B14","doi-asserted-by":"crossref","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","article-title":"The Sequence Alignment\/Map format and SAMtools","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B15","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1093\/bib\/bbq015","article-title":"A survey of sequence alignment algorithms for next-generation sequencing","volume":"11","author":"Li","year":"2010","journal-title":"Brief. Bioinf"},{"key":"2023063012495568000_btx189-B16","doi-asserted-by":"crossref","first-page":"1851","DOI":"10.1101\/gr.078212.108","article-title":"Mapping short DNA sequencing reads and calling variants using mapping quality scores","volume":"18","author":"Li","year":"2008","journal-title":"Genome Res"},{"key":"2023063012495568000_btx189-B17","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1093\/bioinformatics\/btn025","article-title":"SOAP: short oligonucleotide alignment program","volume":"24","author":"Li","year":"2008","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B18","doi-asserted-by":"crossref","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","article-title":"SOAP2: an improved ultrafast tool for short read alignment","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B19","doi-asserted-by":"crossref","DOI":"10.1093\/nar\/gkt214","article-title":"The Subread aligner: fast, accurate and scalable read mapping by seed-and-vote","volume":"41","author":"Liao","year":"2013","journal-title":"Nucleic Acids Res"},{"key":"2023063012495568000_btx189-B20","doi-asserted-by":"crossref","first-page":"2431","DOI":"10.1093\/bioinformatics\/btn416","article-title":"ZOOM! Zillions of oligos mapped","volume":"24","author":"Lin","year":"2008","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B21","doi-asserted-by":"crossref","first-page":"1830","DOI":"10.1093\/bioinformatics\/bts276","article-title":"CUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform","volume":"28","author":"Liu","year":"2012","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B22","doi-asserted-by":"crossref","first-page":"1725","DOI":"10.1101\/gr.194201","article-title":"SSAHA: a fast search method for large DNA databases","volume":"11","author":"Ning","year":"2001","journal-title":"Genome Res"},{"key":"2023063012495568000_btx189-B23","doi-asserted-by":"crossref","DOI":"10.1371\/journal.pcbi.1000386","article-title":"SHRiMP: accurate mapping of short color-space reads","volume":"5","author":"Rumble","year":"2009","journal-title":"Plos Comput. Biol"},{"key":"2023063012495568000_btx189-B24","doi-asserted-by":"crossref","first-page":"1363","DOI":"10.1093\/bioinformatics\/btp236","article-title":"CloudBurst: highly sensitive read mapping with MapReduce","volume":"25","author":"Schatz","year":"2009","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B25","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2105-9-128","article-title":"Using quality scores and longer reads improves accuracy of Solexa read mapping","volume":"9","author":"Smith","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023063012495568000_btx189-B26","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1038\/nature15394","article-title":"An integrated map of structural variation in 2,504 human genomes","volume":"526","author":"Sudmant","year":"2015","journal-title":"Nature"},{"key":"2023063012495568000_btx189-B27","doi-asserted-by":"crossref","first-page":"3396","DOI":"10.1093\/bioinformatics\/btu553","article-title":"Acceleration of short and long DNA read mapping without loss of accuracy using suffix array","volume":"30","author":"Tarraga","year":"2014","journal-title":"Bioinformatics"},{"key":"2023063012495568000_btx189-B28","article-title":"A block-sorting lossless data compression algorithm","volume":"124","author":"Wheeler","year":"1994","journal-title":"SRC Res. Rep"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/15\/2281\/50756437\/bioinformatics_33_15_2281.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/33\/15\/2281\/50756437\/bioinformatics_33_15_2281.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,30]],"date-time":"2023-06-30T12:50:20Z","timestamp":1688129420000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/33\/15\/2281\/3100437"}},"subtitle":[],"editor":[{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2017,4,4]]},"references-count":28,"journal-issue":{"issue":"15","published-print":{"date-parts":[[2017,8,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btx189","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2017,8,1]]},"published":{"date-parts":[[2017,4,4]]}}}