A Compressive Seeding Algorithm in Conjunction with Reordering-based Compression

Overview

Journal Bioinformatics

Publisher Oxford University Press

Specialty Biology

Date 2024 Feb 20

PMID 38377404

Authors

Fahu Ji

Qian Zhou

Jue Ruan

Zexuan Zhu

Xianming Liu

Affiliations

Soon will be listed here.

Abstract

Motivation: Seeding is a rate-limiting stage in sequence alignment for next-generation sequencing reads. The existing optimization algorithms typically utilize hardware and machine-learning techniques to accelerate seeding. However, an efficient solution provided by professional next-generation sequencing compressors has been largely overlooked by far. In addition to achieving remarkable compression ratios by reordering reads, these compressors provide valuable insights for downstream alignment that reveal the repetitive computations accounting for more than 50% of seeding procedure in commonly used short read aligner BWA-MEM at typical sequencing coverage. Nevertheless, the exploited redundancy information is not fully realized or utilized.

Results: In this study, we present a compressive seeding algorithm, named CompSeed, to fill the gap. CompSeed, in collaboration with the existing reordering-based compression tools, finishes the BWA-MEM seeding process in about half the time by caching all intermediate seeding results in compact trie structures to directly answer repetitive inquiries that frequently cause random memory accesses. Furthermore, CompSeed demonstrates better performance as sequencing coverage increases, as it focuses solely on the small informative portion of sequencing reads after compression. The innovative strategy highlights the promising potential of integrating sequence compression and alignment to tackle the ever-growing volume of sequencing data.

Availability And Implementation: CompSeed is available at https://github.com/i-xiaohu/CompSeed.

References

Chandak S, Tatwawadi K, Ochoa I, Hernaez M, Weissman T . SPRING: a next-generation compressor for FASTQ data. Bioinformatics. 2018; 35(15):2674-2676. PMC: 6662292. DOI: 10.1093/bioinformatics/bty1015. View

Liu Y, Li J . Hamming-shifting graph of genomic short reads: Efficient construction and its application for compression. PLoS Comput Biol. 2021; 17(7):e1009229. PMC: 8321399. DOI: 10.1371/journal.pcbi.1009229. View

Li H . Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly. Bioinformatics. 2012; 28(14):1838-44. PMC: 3389770. DOI: 10.1093/bioinformatics/bts280. View

Lin H, Hsu W . Kart: a divide-and-conquer algorithm for NGS read alignment. Bioinformatics. 2017; 33(15):2281-2287. PMC: 5860120. DOI: 10.1093/bioinformatics/btx189. View

Langmead B, Salzberg S . Fast gapped-read alignment with Bowtie 2. Nat Methods. 2012; 9(4):357-9. PMC: 3322381. DOI: 10.1038/nmeth.1923. View

Loh P, Baym M, Berger B . Compressive genomics. Nat Biotechnol. 2012; 30(7):627-30. DOI: 10.1038/nbt.2241. View

Altschul S, Madden T, Schaffer A, Zhang J, Zhang Z, Miller W . Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res. 1997; 25(17):3389-402. PMC: 146917. DOI: 10.1093/nar/25.17.3389. View

Wilton R, Szalay A . Performance optimization in DNA short-read alignment. Bioinformatics. 2022; 38(8):2081-2087. PMC: 10060706. DOI: 10.1093/bioinformatics/btac066. View

Liu Y, Yu Z, Dinger M, Li J . Index suffix-prefix overlaps by (w, k)-minimizer to generate long contigs for reads compression. Bioinformatics. 2018; 35(12):2066-2074. DOI: 10.1093/bioinformatics/bty936. View

10.

Zhu Z, Li L, Zhang Y, Yang Y, Yang X . CompMap: a reference-based compression program to speed up read mapping to related reference sequences. Bioinformatics. 2014; 31(3):426-8. DOI: 10.1093/bioinformatics/btu656. View

11.

Li H, Durbin R . Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics. 2009; 25(14):1754-60. PMC: 2705234. DOI: 10.1093/bioinformatics/btp324. View

12.

Liu Y, Schmidt B, Maskell D . CUDASW++2.0: enhanced Smith-Waterman protein database search on CUDA-enabled GPUs based on SIMT and virtualized SIMD abstractions. BMC Res Notes. 2010; 3:93. PMC: 2907862. DOI: 10.1186/1756-0500-3-93. View

13.

Wang T, Antonacci-Fulton L, Howe K, Lawson H, Lucas J, Phillippy A . The Human Pangenome Project: a global resource to map genomic diversity. Nature. 2022; 604(7906):437-446. PMC: 9402379. DOI: 10.1038/s41586-022-04601-8. View

14.

Darby C, Gaddipati R, Schatz M, Langmead B . Vargas: heuristic-free alignment for assessing linear and graph read aligners. Bioinformatics. 2020; 36(12):3712-3718. PMC: 7320598. DOI: 10.1093/bioinformatics/btaa265. View

15.

Jung Y, Han D . BWA-MEME: BWA-MEM emulated with a machine learning approach. Bioinformatics. 2022; 38(9):2404-2413. DOI: 10.1093/bioinformatics/btac137. View

16.

Kirsche M, Das A, Schatz M . Sapling: accelerating suffix array queries with learned data models. Bioinformatics. 2020; 37(6):744-749. DOI: 10.1093/bioinformatics/btaa911. View

17.

Cock P, Fields C, Goto N, Heuer M, Rice P . The Sanger FASTQ file format for sequences with quality scores, and the Solexa/Illumina FASTQ variants. Nucleic Acids Res. 2009; 38(6):1767-71. PMC: 2847217. DOI: 10.1093/nar/gkp1137. View

18.

Marco-Sola S, Sammeth M, Guigo R, Ribeca P . The GEM mapper: fast, accurate and versatile alignment by filtration. Nat Methods. 2012; 9(12):1185-8. DOI: 10.1038/nmeth.2221. View

19.

Yorukoglu D, Yu Y, Peng J, Berger B . Compressive mapping for next-generation sequencing. Nat Biotechnol. 2016; 34(4):374-6. PMC: 5080835. DOI: 10.1038/nbt.3511. View

20.

Kent W . BLAT--the BLAST-like alignment tool. Genome Res. 2002; 12(4):656-64. PMC: 187518. DOI: 10.1101/gr.229202. View