{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,7]],"date-time":"2026-02-07T18:01:09Z","timestamp":1770487269220,"version":"3.49.0"},"reference-count":34,"publisher":"Oxford University Press (OUP)","issue":"21","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: As high-throughput sequencing (HTS) technology becomes ubiquitous and the volume of data continues to rise, HTS read alignment is becoming increasingly rate-limiting, which keeps pressing the development of novel read alignment approaches. Moreover, promising novel applications of HTS technology require aligning reads to multiple genomes instead of a single reference; however, it is still not viable for the state-of-the-art aligners to align large numbers of reads to multiple genomes.<\/jats:p>\n               <jats:p>Results: We propose de Bruijn Graph-based Aligner (deBGA), an innovative graph-based seed-and-extension algorithm to align HTS reads to a reference genome that is organized and indexed using a de Bruijn graph. With its well-handling of repeats, deBGA is substantially faster than state-of-the-art approaches while maintaining similar or higher sensitivity and accuracy. This makes it particularly well-suited to handle the rapidly growing volumes of sequencing data. Furthermore, it provides a promising solution for aligning reads to multiple genomes and graph-based references in HTS applications.<\/jats:p>\n               <jats:p>Availability and Implementation: deBGA is available at: https:\/\/github.com\/hitbc\/deBGA .<\/jats:p>\n               <jats:p>Contact: \u00a0ydwang@hit.edu.cn<\/jats:p>\n               <jats:p>Supplementary information : Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btw371","type":"journal-article","created":{"date-parts":[[2016,7,5]],"date-time":"2016-07-05T01:59:34Z","timestamp":1467683974000},"page":"3224-3232","source":"Crossref","is-referenced-by-count":84,"title":["deBGA: read alignment with de Bruijn graph-based seed and extension"],"prefix":"10.1093","volume":"32","author":[{"given":"Bo","family":"Liu","sequence":"first","affiliation":[{"name":"1 Center for Bioinformatics, Harbin Institute of Technology, Harbin, Heilongjiang 150001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongzhe","family":"Guo","sequence":"additional","affiliation":[{"name":"1 Center for Bioinformatics, Harbin Institute of Technology, Harbin, Heilongjiang 150001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Brudno","sequence":"additional","affiliation":[{"name":"2 Department of Computer Science, University of Toronto, ON M5S 3G4, Canada"},{"name":"3 Genetics and Genome Biology Program, The Hospital for Sick Children, Toronto, ON M5G 1L7, Canada"},{"name":"4 Centre for Computational Medicine, The Hospital for Sick Children, Toronto, ON M5G 1L7, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yadong","family":"Wang","sequence":"additional","affiliation":[{"name":"1 Center for Bioinformatics, Harbin Institute of Technology, Harbin, Heilongjiang 150001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2016,7,4]]},"reference":[{"key":"2023020113513259900_btw371-B1","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1038\/nature11632","article-title":"An integrated map of genetic variation from 1,092 human genomes","volume":"491","author":"1000 Genomes Project Consortium","year":"2012","journal-title":"Nature"},{"key":"2023020113513259900_btw371-B2","doi-asserted-by":"crossref","first-page":"180.","DOI":"10.12688\/f1000research.6743.1","article-title":"Re-analysis of metagenomic sequences from acute flaccid myelitis patients reveals alternatives to enterovirus D68 infection","volume":"4","author":"Breitwieser","year":"2015","journal-title":"F1000Res"},{"key":"2023020113513259900_btw371-B3","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1038\/ng.806","article-title":"A framework for variation discovery and genotyping using next-generation DNA sequencing data","volume":"43","author":"DePristo","year":"2011","journal-title":"Nat. Genet"},{"key":"2023020113513259900_btw371-B4","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1038\/nrg3226","article-title":"Transforming clinical microbiology with bacterial genome sequencing","volume":"13","author":"Didelot","year":"2012","journal-title":"Nat. Rev. Genet"},{"key":"2023020113513259900_btw371-B5","doi-asserted-by":"crossref","first-page":"682","DOI":"10.1038\/ng.3257","article-title":"Improved genome inference in the MHC using a population reference graph","volume":"47","author":"Dilthey","year":"2015","journal-title":"Nat. Genet"},{"key":"2023020113513259900_btw371-B6","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1093\/bioinformatics\/bts635","article-title":"STAR: ultrafast universal RNA-seq aligner","volume":"29","author":"Dobin","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020113513259900_btw371-B7","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/1471-2105-9-11","article-title":"SeqAn: an efficient, generic C\u2002++ library for sequence analysis","volume":"9","author":"D\u00f6ring","year":"2008","journal-title":"BMC Bioinformatics"},{"key":"2023020113513259900_btw371-B8","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1038\/nrg3624","article-title":"Bacterial genome sequencing in the clinic: bioinformatic challenges and solutions","volume":"15","author":"Fricke","year":"2014","journal-title":"Nat. Rev. Genet"},{"key":"2023020113513259900_btw371-B9","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1038\/nature10414","article-title":"Multiple reference genomes and transcriptomes for Arabidopsis thaliana","volume":"477","author":"Gan","year":"2011","journal-title":"Nature"},{"key":"2023020113513259900_btw371-B10","doi-asserted-by":"crossref","first-page":"1513","DOI":"10.1073\/pnas.1017351108","article-title":"High-quality draft assemblies of mammalian genomes from massively parallel sequence data","volume":"108","author":"Gnerre","year":"2011","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023020113513259900_btw371-B11","doi-asserted-by":"crossref","first-page":"1154","DOI":"10.1101\/gr.135780.111","article-title":"lobSTR: a short tandem repeat profiler for personal genomes","volume":"22","author":"Gymrek","year":"2012","journal-title":"Genome Res"},{"key":"2023020113513259900_btw371-B12","doi-asserted-by":"crossref","first-page":"i361","DOI":"10.1093\/bioinformatics\/btt215","article-title":"Short read alignment with populations of genomes","volume":"29","author":"Huang","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020113513259900_btw371-B13","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1186\/1471-2105-15-99","article-title":"Genome alignment with graph data structures: a comparison","volume":"15","author":"Kehr","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023020113513259900_btw371-B14","author":"Landau","year":"1986"},{"key":"2023020113513259900_btw371-B15","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":"2023020113513259900_btw371-B16","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":"2023020113513259900_btw371-B17","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":"2023020113513259900_btw371-B18","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 Bioinform"},{"key":"2023020113513259900_btw371-B19","author":"Li","year":"2013"},{"key":"2023020113513259900_btw371-B20","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1038\/nmeth.2221","article-title":"The GEM mapper: fast, accurate and versatile alignment by filtration","volume":"9","author":"Marco-Sola","year":"2012","journal-title":"Nat. Methods"},{"key":"2023020113513259900_btw371-B21","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1016\/j.gde.2005.09.006","article-title":"The microbial pan-genome","volume":"15","author":"Medini","year":"2005","journal-title":"Curr. Opin. Genet. Dev"},{"key":"2023020113513259900_btw371-B22","doi-asserted-by":"crossref","first-page":"2366","DOI":"10.1093\/bioinformatics\/bts450","article-title":"Fast and accurate read alignment for resequencing","volume":"28","author":"Mu","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020113513259900_btw371-B23","author":"Paten","year":"2014"},{"key":"2023020113513259900_btw371-B24","doi-asserted-by":"crossref","first-page":"D756","DOI":"10.1093\/nar\/gkt1114","article-title":"RefSeq: an update on mammalian reference sequences","volume":"42","author":"Pruitt","year":"2014","journal-title":"Nucleic Acids Res"},{"key":"2023020113513259900_btw371-B25","doi-asserted-by":"crossref","first-page":"2336","DOI":"10.1101\/gr.2657504","article-title":"A novel method for multiple alignment of sequences with repeated and shuffled elements","volume":"14","author":"Raphael","year":"2004","journal-title":"Genome Res"},{"key":"2023020113513259900_btw371-B26","doi-asserted-by":"crossref","first-page":"i333","DOI":"10.1093\/bioinformatics\/bts378","article-title":"DELLY: structural variant discovery by integrated paired-end and split-read analysis","volume":"28","author":"Rausch","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020113513259900_btw371-B28","doi-asserted-by":"crossref","first-page":"R98","DOI":"10.1186\/gb-2009-10-9-r98","article-title":"Simultaneous alignment of short reads against multiple genomes","volume":"10","author":"Schneeberger","year":"2009","journal-title":"Genome Biol"},{"key":"2023020113513259900_btw371-B29","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1093\/nar\/29.1.308","article-title":"dbSNP: the NCBI database of genetic variation","volume":"29","author":"Sherry","year":"2001","journal-title":"Nucleic Acids Res"},{"key":"2023020113513259900_btw371-B30","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1109\/TCBB.2013.2297101","article-title":"Indexing graphs for path queries with applications in genome research","volume":"11","author":"Siren","year":"2014","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020113513259900_btw371-B31","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":"2023020113513259900_btw371-B32","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1038\/nrg3117","article-title":"Repetitive DNA and next-generation sequencing: computational challenges and solutions","volume":"13","author":"Treangen","year":"2012","journal-title":"Nat. Rev. Genet"},{"key":"2023020113513259900_btw371-B33","author":"Valenzuela","year":"2015"},{"key":"2023020113513259900_btw371-B34","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1038\/nature07484","article-title":"The diploid genome sequence of an Asian individual","volume":"456","author":"Wang","year":"2008","journal-title":"Nature"},{"key":"2023020113513259900_btw371-B35","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1038\/nbt.2835","article-title":"Integrating human sequence data sets provides a resource of benchmark SNP and indel genotype calls","volume":"32","author":"Zook","year":"2014","journal-title":"Nat. Biotechnol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/21\/3224\/49021959\/bioinformatics_32_21_3224.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/21\/3224\/49021959\/bioinformatics_32_21_3224.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T23:54:19Z","timestamp":1675295659000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/21\/3224\/2415064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,4]]},"references-count":34,"journal-issue":{"issue":"21","published-print":{"date-parts":[[2016,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw371","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,11,1]]},"published":{"date-parts":[[2016,7,4]]}}}