|Table of Contents|

Research on Sequence Alignment Algorithm Based on Optimized BWT Indexing Technique(PDF)

南京师范大学学报（工程技术版）[ISSN:1006-6977/CN:61-1281/TN]

Issue:
2024年04期
Page:
37-45
Research Field:
计算机科学与技术
Publishing date:

Info

Title:
Research on Sequence Alignment Algorithm Based on Optimized BWT Indexing Technique
Author(s):
Hu Chunling1; Zhao Junjie2; Yao Mengyuan1; Gao Huanhuan1; Zhu Yihang1; Wang Shaohong1
(1.School of Artificial Intelligence and Big Data,Hefei University,Hefei 230031,China)
(2.School of Computer Science and Artificial Intelligence,Zhengzhou University,Zhengzhou 450001,China)
Keywords:
sequence alignment; BWT index; difference cover mod 3; suffix array
PACS:
TP181
DOI:
10.3969/j.issn.1672-1292.2024.04.004
Abstract:
Large-scale gene sequence alignment is the most important fundamental problem in bioinformatics. Based on the mainstream research of BWT index technology,the paper proposes a new multi-order mixed BWT index method,which dynamically selects the appropiate multi-bit indexing according to the length of the sequence to be compared. The experimental results show that the improved method can effectively reduce the number of comparison and calculation times,reduce the time complexity of the index algorithm,and significantly improve the efficiency of sequence comparison. In the process of constructing BWT(S)string,this paper uses DC3(difference cover mod 3)algorithm to construct the suffix array. Experiments show that DC3 algorithm has better time performance compared to Binary Lifting.

References:

[1]SARKAR A,GHOSH S,RAY S S. A hardware-based memory-efficient solution for pair-wise compact sequence alignment[J]. IETE Journal of Research,2023,69(6):3638-3649.
[2]刘济晗. 三代RNA测序序列的比对和分析工具[D]. 哈尔滨:哈尔滨工业大学,2018.
[3]LI R Q,LI Y R,KRISTIANSEN K,et al. SOAP:short oligonucleotide alignment program[J]. Bioinformatics,2008,24(5):713-714.
[4]CAMPAGNA D,ALBIERO A,BILARDI A,et al. PASS:a program to align short sequences[J]. Bioinformatics,2009,25(7):967-968.
[5]SMITH A D,XUAN Z Y,ZHANG M Q. Using quality scores and longer reads improves accuracy of Solexa read mapping[J]. BMC Bioinformatics,2008,9(1):128.
[6]SSERWADDA I,MBOOWA G. rMAP:The rapid microbial analysis pipeline for ESKAPE bacterial group whole-genome sequence data[J]. Microbial Genomics,2021,7(6):000583.
[7]LI H,RUAN J,DURBIN R. Mapping short DNA sequencing reads and calling variants using mapping quality scores[J]. Genome Research,2008,18(11):1851-1858.
[8]RUMBLE S M,LACROUTE P,DALCA A V,et al. SHRiMP:accurate mapping of short color-space reads[J]. PLoS Computational Biology,2009,5(5):e1000386.
[9]BURROWS M J,WHEELER D. A block-sorting lossless data compression algorithm:SRC Research Report 124[R]. Palo Alto,CA,USA:Digital Systems Research Center,1994.
[10]FUENTES-SEPAM'U1LVEDA J,NAVARRO G,NEKRICH Y. Parallel computation of the Burrows Wheeler Transform in compact space[J]. Theoretical Computer Science,2020,812:123-136.
[11]GAGIE T,MANZINI G,SIRÉN J. Wheeler graphs:A framework for BWT-based data structures[J]. Theoretical Computer Science,2017,698:67-78.
[12]LANGMEAD B,TRAPNELL C,POP M,et al. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome[J]. Genome Biology,2009,10(3):R25.
[13]LANGMEAD B,SALZBERG S L. Fast gapped-read alignment with Bowtie 2[J]. Nature Methods,2012,9(4):357-359.
[14]LI H,DURBIN R. Fast and accurate long-read alignment with Burrows-Wheeler transform[J]. Bioinformatics,2010,26(5):589-595.
[15]KEEL B N,SNELLING W M. Comparison of burrows-wheeler transform-based mapping algorithms used in high-throughput whole-genome sequencing:application to illumina data for livestock genomes[J]. Frontiers in Genetics,2018(9):35.
[16]赵雅男,徐云,程昊宇. 序列比对算法中的 BW 变换索引技术研究及其改进[J]. 计算机工程,2016,42(1):282-286.
[17]CHANG C H,CHOU M T,WU Y C,et al. sBWT:Memory efficient implementation of the hardware-acceleration-friendly Schindler transform for the fast biological sequence mapping[J]. Bioinformatics,2016,32(22):3498-3500.
[18]EGIDI L,LOUZA F A,MANZINI G,et al. External memory BWT and LCP computation for sequence collections with applications[J]. Algorithms for Molecular Biology,2019,14:6.
[19]LIU Y C,SCHMIDT B,MASKELL D. CUSHAW:a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform[J]. Bioinformatics,2012,28(14):1830-1837.
[20]KUMAR S,AGARWAL S,RANVIJAY. Burrows wheeler transform and wavelet tree based retrieval of genome sequence in an indexed genome database[J]. Recent Advances in Computer Science and Communications,2020,13(6):1213-1220.
[21]SILVA M,PRATAS D,PINHO A J. AC2:an efficient protein sequence compression tool using artificial neural networks and cache-hash models[J]. Entropy(Basel),2021,23(5):530.
[22]CHEN Y,YOU D L,ZHANG T J,et al. SLDMS:a tool for calculating the overlapping regions of sequences[J]. Frontiers in Plant Science,2022,12:813036.
[23]BINGMANN T. Scalable string and suffix sorting:algorithms,techniques,and tools[EB/OL].(2018-08-02)[2024-05-12]. https://doi.org/10.48550/arXiv.1808.00963.
[24]ZHENG W B,CHEN J,DOAK T G,et al. ADFinder:accurate detection of programmed DNA elimination using NGS high-throughput sequencing data[J]. Bioinformatics,2020,36(12):3632-3636.
[25]KIM Y,CHOI S,JEONG J,et al. Data dependency reduction for high-performance FPGA implementation of DEFLATE compression algorithm[J]. Journal of Systems Architecture,2019,98:41-52.
[26]GRIEBLER D,HOFFMANN R B,DANELUTTO M,et al. High-level and productive stream parallelism for Dedup,Ferret,and Bzip2[J]. International Journal of Parallel Programming,2019,47(2):253-271.

Memo

Memo:
-
Last Update: 2024-12-15