EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Columba: fast approximate pattern matching with optimized search schemes

Luca Renders iD, Lore Depuydt, Travis Gagie iD, Jan Fostier iD

Bioinformatics · 2025

DOI: 10.1093/bioinformatics/btaf652 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Bioinformatics, 2025. Verfasst von Luca Renders und 3 weiteren Autor:innen. Beteiligte Einrichtung: Department of Information Technology-IDLab, Ghent University-imec, Ghent 9052, Belgium. Hauptthemen laut MEDLINE: Software, Sequence Alignment, Sequence Analysis, DNA. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 41 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Research Foundation-Flanders (FWO), Research Foundation—Flanders.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Motivation 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. Results 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. Availability and implementation 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.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

SoftwareSequence AlignmentSequence Analysis, DNAHumansGenome, HumanAlgorithmsHigh-Throughput Nucleotide SequencingComputational Biology

Autor:innen und Institutionen

  • Department of Information Technology-IDLab, Ghent University-imec, Ghent 9052, Belgium.
  • Faculty of Computer Science, Dalhousie University, Halifax, NS B3H 4R2, Canada.

ORCID-Profile: Luca Renders, Travis Gagie, Jan Fostier

Förderung

  • Research Foundation-Flanders (FWO)
  • Research Foundation—Flanders

Zitieren

APA

Renders, L., Depuydt, L., Gagie, T., & Fostier, J. (2025). Columba: fast approximate pattern matching with optimized search schemes. Bioinformatics. https://doi.org/10.1093/bioinformatics/btaf652

Vancouver

Renders L, Depuydt L, Gagie T, Fostier J. Columba: fast approximate pattern matching with optimized search schemes. Bioinformatics. 2025. doi:10.1093/bioinformatics/btaf652

BibTeX
@article{Renders2025,
  author = {Renders, Luca and Depuydt, Lore and Gagie, Travis and Fostier, Jan},
  title = {Columba: fast approximate pattern matching with optimized search schemes},
  journal = {Bioinformatics},
  year = {2025},
  doi = {10.1093/bioinformatics/btaf652}
}
Kostenlos starten →