{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T20:34:57Z","timestamp":1772138097171,"version":"3.50.1"},"reference-count":14,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T00:00:00Z","timestamp":1571097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100004807","name":"DFG","doi-asserted-by":"publisher","award":["OH 53\/7-1"],"award-info":[{"award-number":["OH 53\/7-1"]}],"id":[{"id":"10.13039\/100004807","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,3,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>In resequencing experiments, a high-throughput sequencer produces DNA-fragments (called reads) and each read is then mapped to the locus in a reference genome at which it fits best. Currently dominant read mappers are based on the Burrows\u2013Wheeler transform (BWT). A read can be mapped correctly if it is similar enough to a substring of the reference genome. However, since the reference genome does not represent all known variations, read mapping tends to be biased towards the reference and mapping errors may thus occur. To cope with this problem, Huang et al. encoded single nucleotide polymorphisms (SNPs) in a BWT by the International Union of Pure and Applied Chemistry (IUPAC) nucleotide code. In a different approach, Maciuca et al. provided a \u2018natural encoding\u2019 of SNPs and other genetic variations in a BWT. However, their encoding resulted in a significantly increased alphabet size (the modified alphabet can have millions of new symbols, which usually implies a loss of efficiency). Moreover, the two approaches do not handle all known kinds of variation.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>In this article, we propose a method that is able to encode many kinds of genetic variation (SNPs, multi-nucleotide polymorphisms, insertions or deletions, duplications, transpositions, inversions and copy-number variation) in a BWT. It takes the best of both worlds: SNPs are encoded by the IUPAC nucleotide code as in Huang et al. (2013, Short read alignment with populations of genomes. Bioinformatics, 29, i361\u2013i370) and the encoding of the other kinds of genetic variation relies on the idea introduced in Maciuca et al. (2016, A natural encoding of genetic variation in a Burrows-Wheeler transform to enable mapping and genome inference. In: Proceedings of the 16th International Workshop on Algorithms in Bioinformatics, Volume 9838 of Lecture Notes in Computer Science, pp. 222\u2013233. Springer). In contrast to Maciuca et al., however, we use only one additional symbol. This symbol marks variant sites in a chromosome and delimits multiple variants, which are added at the end of the \u2018marked chromosome\u2019. We show how the backward search algorithm, which is used in BWT-based read mappers, can be modified in such a way that it can cope with the genetic variation encoded in the BWT. We implemented our method and compared it with BWBBLE and gramtools.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>https:\/\/www.uni-ulm.de\/in\/theo\/research\/seqana\/.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btz782","type":"journal-article","created":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T15:31:09Z","timestamp":1570807869000},"page":"1413-1419","source":"Crossref","is-referenced-by-count":6,"title":["An improved encoding of genetic variation in a Burrows\u2013Wheeler transform"],"prefix":"10.1093","volume":"36","author":[{"given":"Thomas","family":"B\u00fcchler","sequence":"first","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University , Ulm 89069, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enno","family":"Ohlebusch","sequence":"additional","affiliation":[{"name":"Institute of Theoretical Computer Science, Ulm University , Ulm 89069, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,10,15]]},"reference":[{"key":"2023060910263298800_btz782-B1","volume-title":"A Block-Sorting Lossless Data Compression Algorithm","author":"Burrows","year":"1994"},{"key":"2023060910263298800_btz782-B2","doi-asserted-by":"crossref","first-page":"3021","DOI":"10.1093\/nar\/13.9.3021","article-title":"Nomenclature for incompletely specified bases in nucleic acid sequences: recommendations 1984","volume":"13","author":"Cornish-Bowden","year":"1985","journal-title":"Nucleic Acids Res"},{"key":"2023060910263298800_btz782-B3","first-page":"390","author":"Ferragina","year":"2000"},{"key":"2023060910263298800_btz782-B4","first-page":"326","author":"Gog","year":"2014"},{"key":"2023060910263298800_btz782-B5","first-page":"841","author":"Grossi","year":"2003"},{"key":"2023060910263298800_btz782-B6","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":"2023060910263298800_btz782-B7","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1038\/35057062","article-title":"Initial sequencing and analysis of the human genome","volume":"409","author":"Lander","year":"2001","journal-title":"Nature"},{"key":"2023060910263298800_btz782-B8","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with bowtie2","volume":"9","author":"Langmead","year":"2012","journal-title":"Nat. Methods"},{"key":"2023060910263298800_btz782-B9","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":"2023060910263298800_btz782-B10","first-page":"222","author":"Maciuca","year":"2016"},{"key":"2023060910263298800_btz782-B11","volume-title":"Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction","author":"Ohlebusch","year":"2013"},{"key":"2023060910263298800_btz782-B12","doi-asserted-by":"crossref","first-page":"4.","DOI":"10.1145\/1242471.1242472","article-title":"A taxonomy of suffix array construction algorithms","volume":"39","author":"Puglisi","year":"2007","journal-title":"ACM Comput. Surv"},{"key":"2023060910263298800_btz782-B13","doi-asserted-by":"crossref","first-page":"e127.","DOI":"10.1093\/nar\/gks425","article-title":"A new strategy to reduce allelic bias in RNA-Seq readmapping","volume":"40","author":"Satya","year":"2012","journal-title":"Nucleic Acids Res"},{"key":"2023060910263298800_btz782-B14","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1038\/nature15393","article-title":"A global reference for human genetic variation","volume":"526","year":"2015","journal-title":"Nature"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btz782\/31079667\/btz782.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/5\/1413\/50552792\/bioinformatics_36_5_1413.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/5\/1413\/50552792\/bioinformatics_36_5_1413.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T06:26:47Z","timestamp":1686292007000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/5\/1413\/5587763"}},"subtitle":[],"editor":[{"given":"Alfonso","family":"Valencia","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2019,10,15]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,3,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz782","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/658716","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,3]]},"published":{"date-parts":[[2019,10,15]]}}}