{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T16:20:15Z","timestamp":1780330815906,"version":"3.54.1"},"reference-count":41,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"vor","delay-in-days":4,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Research Foundation\u2014Flanders","award":["1SE7822N"],"award-info":[{"award-number":["1SE7822N"]}]},{"name":"Research Foundation\u2014Flanders","award":["1117322N"],"award-info":[{"award-number":["1117322N"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,12,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Aligning sequencing reads to reference genomes is a fundamental task in bioinformatics. Aligners can be classified as lossy or lossless: lossy aligners prioritize speed by reporting only one or a few high-scoring alignments, whereas lossless aligners output all optimal alignments, ensuring completeness and sensitivity.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>This paper introduces Columba, a high-performance lossless aligner tailored for Illumina sequencing data. Columba processes single or paired-end reads in FASTQ format and outputs alignments in SAM format. By utilizing advanced search schemes and bit-parallel alignment techniques, Columba achieves exceptional speed. Columba is available in two variants. The first, based on the bidirectional FM-index, prioritizes speed. The second, Columba RLC, uses run-length compression using a bidirectional move structure, significantly reducing memory usage for large, repetitive datasets like pan-genomes. Benchmarks on the human genome, as well as bacterial and human pan-genome datasets, demonstrate that Columba is much faster than existing lossless aligners and even competitive with lossy tools. We integrated Columba into the OptiType HLA genotyping pipeline, where it substantially reduced computational time while maintaining accuracy. These results position Columba as a versatile, state-of-the-art tool for high-sensitivity genomic analyses.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>The source code of Columba is available at https:\/\/github.com\/biointec\/columba under AGPL license. Scripts to reproduce the benchmarks and analyses are available at https:\/\/doi.org\/10.5281\/zenodo.15849246.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaf652","type":"journal-article","created":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T12:30:22Z","timestamp":1764592222000},"source":"Crossref","is-referenced-by-count":2,"title":["Columba: fast approximate pattern matching with optimized search schemes"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2244-1427","authenticated-orcid":false,"given":"Luca","family":"Renders","sequence":"first","affiliation":[{"name":"Department of Information Technology\u2014IDLab, Ghent University\u2014imec , Ghent 9052,","place":["Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lore","family":"Depuydt","sequence":"additional","affiliation":[{"name":"Department of Information Technology\u2014IDLab, Ghent University\u2014imec , Ghent 9052,","place":["Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3689-327X","authenticated-orcid":false,"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Dalhousie University , Halifax, NS B3H 4R2,","place":["Canada"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9994-8269","authenticated-orcid":false,"given":"Jan","family":"Fostier","sequence":"additional","affiliation":[{"name":"Department of Information Technology\u2014IDLab, Ghent University\u2014imec , Ghent 9052,","place":["Belgium"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"2025122310080483900_btaf652-B1","doi-asserted-by":"crossref","first-page":"102696","DOI":"10.1016\/j.isci.2021.102696","article-title":"Pan-genomic matching statistics for targeted nanopore sequencing","volume":"24","author":"Ahmed","year":"2021","journal-title":"iScience"},{"key":"2025122310080483900_btaf652-B2","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1186\/s13059-023-02958-1","article-title":"SPUMONI 2: improved classification using a pangenome index of minimizer digests","volume":"24","author":"Ahmed","year":"2023","journal-title":"Genome Biol"},{"key":"2025122310080483900_btaf652-B3","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1186\/s13015-019-0148-5","article-title":"Prefix-free parsing for building big BWTs","volume":"14","author":"Boucher","year":"2019","journal-title":"Algorithms Mol Biol"},{"key":"2025122310080483900_btaf652-B4","first-page":"193","author":"Boucher","year":"2021"},{"key":"2025122310080483900_btaf652-B5","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1186\/s12864-023-09351-z","article-title":"Benchmark of tools for in silico prediction of MHC class I and class II genotypes from NGS data","volume":"24","author":"Claeys","year":"2023","journal-title":"BMC Genomics"},{"key":"2025122310080483900_btaf652-B6","doi-asserted-by":"crossref","first-page":"i766","DOI":"10.1093\/bioinformatics\/bty567","article-title":"DREAM-Yara: an exact read mapper for very large databases with short update time","volume":"34","author":"Dadi","year":"2018","journal-title":"Bioinformatics"},{"key":"2025122310080483900_btaf652-B7","doi-asserted-by":"crossref","first-page":"400","DOI":"10.1186\/s12859-023-05531-6","article-title":"Pan-genome de Bruijn graph using the bidirectional FM-index","volume":"24","author":"Depuydt","year":"2023","journal-title":"BMC Bioinformatics"},{"key":"2025122310080483900_btaf652-B8","first-page":"1","author":"Depuydt","year":"2024"},{"key":"2025122310080483900_btaf652-B9","first-page":"390","author":"Ferragina","year":"2000"},{"key":"2025122310080483900_btaf652-B10","first-page":"1459","author":"Gagie","year":"2018"},{"key":"2025122310080483900_btaf652-B11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3375890","article-title":"Fully functional suffix trees and optimal text searching in BWT-runs bounded space","volume":"67","author":"Gagie","year":"2020","journal-title":"J ACM"},{"key":"2025122310080483900_btaf652-B12","first-page":"29","article-title":"A bit-vector algorithm for computing Levenshtein and Damerau edit distances","volume":"10","author":"Hyyr\u00f6","year":"2003","journal-title":"Nord J Comput"},{"key":"2025122310080483900_btaf652-B13","article-title":"FAMOUS: fast approximate string matching using optimum search schemes","author":"Kianfar","year":"2017","journal-title":"CoRR"},{"key":"2025122310080483900_btaf652-B14","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.tcs.2015.10.043","article-title":"Approximate string matching using a bidirectional index","volume":"638","author":"Kucherov","year":"2016","journal-title":"Theor Comput Sci"},{"key":"2025122310080483900_btaf652-B15","first-page":"31","author":"Lam","year":"2009"},{"key":"2025122310080483900_btaf652-B16","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":"2025122310080483900_btaf652-B17","doi-asserted-by":"crossref","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":"Gen Biol"},{"key":"2025122310080483900_btaf652-B18","author":"Li","year":"2013"},{"key":"2025122310080483900_btaf652-B19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/bioinformatics\/btae717","article-title":"BWT construction and search at the terabase scale","volume":"40","author":"Li","year":"2024","journal-title":"Bioinformatics"},{"key":"2025122310080483900_btaf652-B20","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows\u2013Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2025122310080483900_btaf652-B21","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":"2025122310080483900_btaf652-B22","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1038\/s41586-023-05896-x","article-title":"A draft human pangenome reference","volume":"617","author":"Liao","year":"2023","journal-title":"Nature"},{"key":"2025122310080483900_btaf652-B23","first-page":"45","author":"Marco-Sola","year":"2005"},{"key":"2025122310080483900_btaf652-B24","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":"2025122310080483900_btaf652-B25","first-page":"1","author":"Myers","year":"1998"},{"key":"2025122310080483900_btaf652-B26","first-page":"1","author":"Nishimoto","year":"2021"},{"key":"2025122310080483900_btaf652-B27","first-page":"190","author":"Pockrandt","year":"2017"},{"key":"2025122310080483900_btaf652-B28","author":"Pockrandt","year":"2019"},{"key":"2025122310080483900_btaf652-B29","doi-asserted-by":"crossref","first-page":"102687","DOI":"10.1016\/j.isci.2021.102687","article-title":"Dynamic partitioning of search patterns for approximate pattern matching using search schemes","volume":"24","author":"Renders","year":"2021","journal-title":"iScience"},{"key":"2025122310080483900_btaf652-B30","first-page":"419","author":"Renders","year":"2022"},{"key":"2025122310080483900_btaf652-B31","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1089\/cmb.2024.0664","article-title":"Lossless approximate pattern matching: automated design of efficient search schemes","volume":"31","author":"Renders","year":"2024","journal-title":"J Comput Biol"},{"key":"2025122310080483900_btaf652-B32","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1089\/cmb.2021.0290","article-title":"MONI: a pangenomic index for finding maximal exact matches","volume":"29","author":"Rossi","year":"2022","journal-title":"J Comput Biol"},{"key":"2025122310080483900_btaf652-B33","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1101\/gr.213611.116","article-title":"Evaluation of GRCh38 and de novo haploid genome assemblies demonstrates the enduring quality of the reference assembly","volume":"27","author":"Schneider","year":"2017","journal-title":"Genome Res"},{"key":"2025122310080483900_btaf652-B34","author":"Siragusa","year":"2015"},{"key":"2025122310080483900_btaf652-B35","doi-asserted-by":"crossref","first-page":"3310","DOI":"10.1093\/bioinformatics\/btu548","article-title":"OptiType: precision HLA typing from next-generation sequencing data","volume":"30","author":"Szolek","year":"2014","journal-title":"Bioinformatics"},{"key":"2025122310080483900_btaf652-B36","doi-asserted-by":"publisher","author":"Vasimuddin","year":"2019","DOI":"10.1109\/IPDPS.2019.00041"},{"key":"2025122310080483900_btaf652-B37","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.jda.2016.03.002","article-title":"Approximate search of short patterns with high error rates using the 010 lossless seeds","volume":"37","author":"Vroland","year":"2016","journal-title":"J Discret Algorithms"},{"key":"2025122310080483900_btaf652-B38","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1101\/gr.088823.108","article-title":"RazerS - Fast read mapping with sensitivity control","volume":"19","author":"Weese","year":"2009","journal-title":"Genome Res"},{"key":"2025122310080483900_btaf652-B39","doi-asserted-by":"crossref","first-page":"2592","DOI":"10.1093\/bioinformatics\/bts505","article-title":"RazerS 3: faster, fully sensitive read mapping","volume":"28","author":"Weese","year":"2012","journal-title":"Bioinformatics"},{"key":"2025122310080483900_btaf652-B40","doi-asserted-by":"crossref","first-page":"111464","DOI":"10.1016\/j.isci.2024.111464","article-title":"Movi: a fast and cache-efficient full-text pangenome index","volume":"27","author":"Zakeri","year":"2024","journal-title":"iScience"},{"key":"2025122310080483900_btaf652-B41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/gigascience\/gix038","article-title":"Alignment of 1000 genomes project reads to reference assembly GRCh38","volume":"6","author":"Zheng-Bradley","year":"2017","journal-title":"Gigascience"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/12\/btaf652\/65767725\/btaf652.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/12\/btaf652\/65767725\/btaf652.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T15:20:53Z","timestamp":1766503253000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btaf652\/8370107"}},"subtitle":[],"editor":[{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2025,12,1]]},"references-count":41,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaf652","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,12]]},"published":{"date-parts":[[2025,12,1]]},"article-number":"btaf652"}}