Reference-based genome compression using the longest matched substrings with parallelization consideration.
CUDA
Genome compression
Parallelization
Reference-based
Suffix array
Journal
BMC bioinformatics
ISSN: 1471-2105
Titre abrégé: BMC Bioinformatics
Pays: England
ID NLM: 100965194
Informations de publication
Date de publication:
30 Sep 2023
30 Sep 2023
Historique:
received:
02
03
2023
accepted:
26
09
2023
medline:
5
10
2023
pubmed:
1
10
2023
entrez:
30
9
2023
Statut:
epublish
Résumé
A large number of researchers have devoted to accelerating the speed of genome sequencing and reducing the cost of genome sequencing for decades, and they have made great strides in both areas, making it easier for researchers to study and analyze genome data. However, how to efficiently store and transmit the vast amount of genome data generated by high-throughput sequencing technologies has become a challenge for data compression researchers. Therefore, the research of genome data compression algorithms to facilitate the efficient representation of genome data has gradually attracted the attention of these researchers. Meanwhile, considering that the current computing devices have multiple cores, how to make full use of the advantages of the computing devices and improve the efficiency of parallel processing is also an important direction for designing genome compression algorithms. We proposed an algorithm (LMSRGC) based on reference genome sequences, which uses the suffix array (SA) and the longest common prefix (LCP) array to find the longest matched substrings (LMS) for the compression of genome data in FASTA format. The proposed algorithm utilizes the characteristics of SA and the LCP array to select all appropriate LMSs between the genome sequence to be compressed and the reference genome sequence and then utilizes LMSs to compress the target genome sequence. To speed up the operation of the algorithm, we use GPUs to parallelize the construction of SA, while using multiple threads to parallelize the creation of the LCP array and the filtering of LMSs. Experiment results demonstrate that our algorithm is competitive with the current state-of-the-art algorithms in compression ratio and compression time.
Sections du résumé
BACKGROUND
BACKGROUND
A large number of researchers have devoted to accelerating the speed of genome sequencing and reducing the cost of genome sequencing for decades, and they have made great strides in both areas, making it easier for researchers to study and analyze genome data. However, how to efficiently store and transmit the vast amount of genome data generated by high-throughput sequencing technologies has become a challenge for data compression researchers. Therefore, the research of genome data compression algorithms to facilitate the efficient representation of genome data has gradually attracted the attention of these researchers. Meanwhile, considering that the current computing devices have multiple cores, how to make full use of the advantages of the computing devices and improve the efficiency of parallel processing is also an important direction for designing genome compression algorithms.
RESULTS
RESULTS
We proposed an algorithm (LMSRGC) based on reference genome sequences, which uses the suffix array (SA) and the longest common prefix (LCP) array to find the longest matched substrings (LMS) for the compression of genome data in FASTA format. The proposed algorithm utilizes the characteristics of SA and the LCP array to select all appropriate LMSs between the genome sequence to be compressed and the reference genome sequence and then utilizes LMSs to compress the target genome sequence. To speed up the operation of the algorithm, we use GPUs to parallelize the construction of SA, while using multiple threads to parallelize the creation of the LCP array and the filtering of LMSs.
CONCLUSIONS
CONCLUSIONS
Experiment results demonstrate that our algorithm is competitive with the current state-of-the-art algorithms in compression ratio and compression time.
Identifiants
pubmed: 37777730
doi: 10.1186/s12859-023-05500-z
pii: 10.1186/s12859-023-05500-z
pmc: PMC10544193
doi:
Types de publication
Journal Article
Langues
eng
Sous-ensembles de citation
IM
Pagination
369Subventions
Organisme : National Natural Science Foundation of China
ID : 61861045
Informations de copyright
© 2023. BioMed Central Ltd., part of Springer Nature.
Références
Saha S, Rajasekaran S. ERGC: an effificient referential genome compression algorithm. Bioinformatics. 2015;31:3468–75.
doi: 10.1093/bioinformatics/btv399
pubmed: 26139636
pmcid: 4838057
Idoia O, Mikel H, Tsachy W. Idocomp: a compression scheme for assembled genomes. Bioinformatics. 2015;31(5):626–33.
doi: 10.1093/bioinformatics/btu698
Deorowicz S, Danek A, Niemiec M. Gdc 2: compression of large collections of genomes. Sci Rep. 2015;5:11565.
doi: 10.1038/srep11565
pubmed: 26108279
pmcid: 4479802
Deorowicz S, Grabowski S, Ochoa I, et al. Comment on: “ergc: an efficient referential genome compression algorithm.” Bioinformatics. 2016;32:1115–7.
doi: 10.1093/bioinformatics/btv704
pubmed: 26615213
Liu Y, Peng H, Wong L, et al. High-speed and high-ratio referential genome compression. Bioinformatics (Oxford, England). 2017;33:3364–72.
pubmed: 28651329
Shi W, Chen J, Luo M, Chen M, Birol I. High efficiency referential genome compression algorithm. Bioinformatics. 2018;35:2058–65.
doi: 10.1093/bioinformatics/bty934
Tang T, Liu Y, Zhang B, Su B, Li J. Sketch distance-based clustering of chromosomes for large genome database compression. BMC Genom. 2019;20(Suppl 10):1–9.
Yao H, Ji Y, Li K, Liu S, Wang R. Hrcm: an efficient hybrid referential compression method for genomic big data. Biomed Res Int. 2019;2019:1–13.
Vyverman M, et al. essaMEM: finding maximal exact matches using enhanced sparse suffix arrays. Bioinformatics (Oxford, England). 2013;29:802–4.
pubmed: 23349213
Khan Z, Bloom JS, Kruglyak L, Singh M. A practical algorithm for finding maximal exact matches in large sequence datasets using sparse suffix arrays. Bioinformatics. 2009;25:1609–16.
doi: 10.1093/bioinformatics/btp275
pubmed: 19389736
pmcid: 2732316
Chris-Andre L, Burkhard M. Kmacs: the k-mismatch average common substring approach to alignment-free sequence comparison. Bioinformatics. 2014;30(14):2000–8.
doi: 10.1093/bioinformatics/btu331
Grabowski S, Bieniecki W. Copmem: finding maximal exact matches via sampling both genomes. Bioinformatics. 2018;35:677–8.
doi: 10.1093/bioinformatics/bty670
Liu Y, Zhang LY, Li J. Fast detection of maximal exact matches via fixed sampling of query k-mers and bloom filtering of index k-mers. Bioinformatics (Oxford, England). 2019;35:4560–7.
pubmed: 30994891
Beal R, Afrin T, Farheen A, Adjeroh D. A new algorithm for “the LCS problem” with application in compressing genome resequencing data. BMC Genom. 2016;17:369–81.
doi: 10.1186/s12864-016-2793-0
Liu Y, Wong L, Li J. Allowing mutations in maximal matched boosts genome compression performance. Bioinformatics. 2020;36:4675–81.
doi: 10.1093/bioinformatics/btaa572
pubmed: 33118018
Yao H, Hu G, Liu S, et al. SparkGC: spark based genome compression for large collections of genomes. BMC Bioinform. 2022;23:297.
doi: 10.1186/s12859-022-04825-5
Kulla F, Sanders P. Scalable parallel suffix array construction. Parallel Comput. 2007;33:605–12.
doi: 10.1016/j.parco.2007.06.004
Kärkkäinen J, Kärkkäinen J, Sanders P, Sanders P (2003) Simple linear work suffix array construction.
Liao G, Ma L, Zang G, Tang L (2015) Parallel DC3 algorithm for suffix array construction on many-core accelerators. In: 2015 15th IEEE/ACM international symposium on cluster, cloud and grid computing. IEEE.
Büren F, Jünger D, Kobus R, Hundt C, Schmidt B (2019) Suffix array construction on multi-GPU systems. In: The 28th international symposium.
Kasai T, Lee G, Arimura H, Arikawa S, Park K. Linear-time longest-common-prefix computation in suffix arrays and its applications. Berlin: Springer; 2001.
doi: 10.1007/3-540-48194-X_17