Reference Mapping Considering Swaps of Adjacent Bases
Source abstract
Abstract
Since the time of the HGP, research into next-generation sequencing, which can reduce the cost and time of sequence analysis using computer algorithms, has been actively conducted. Mapping is a next-generation sequencing method that identifies sequences by aligning short reads with a reference genome for which sequence information is known. Mapping can be applied to tasks such as SNP calling, motif searches, and gene identification. Research on mapping that utilizes BWT and GPU has been undertaken in order to obtain faster mapping. In this paper, we propose a new mapping algorithm with additional consideration for base swaps. The experimental results demonstrate that when the penalty score for swaps was −1, −2, and −3 in paired-end alignment, for the human whole genome, SOAP3-swap aligned 4667, 2318, and 972 more read pairs, respectively, than SOAP3-dp, and for the drosophila genome, SOAP3-swap aligned 1253, 454, and 129 more read pairs, respectively, than SOAP3-dp. SOAP3-swap has the same functionality as that of SOAP3-dp and also improves the alignment ratio by taking biologically significant swaps into account for the first time.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Genomics and Phylogenetic Studies · Chromosomal and Genetic Variations · Algorithms and Data Compression
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Engineering, Inha University, Incheon 22212, Korea
Samsung Electronics, Suwon 16677, Korea
Electronics and Telecommunications Research Institute, Daejeon 34129, Korea
Funding
National Research Foundation of Korea · Ministry of Science and ICT, South Korea · Inha University
References (33)
Show source-provided references
1. A physical map of the human Y chromosome10.1038/35057170 ↗
2. International Human Genome Sequencing Consortium (2001). Initial sequencing and analysis of the human genome. Nature, 409, 860–921.10.1038/35057062 ↗
3. Sequencing technologies—the next generation10.1038/nrg2626 ↗
4. Evaluation of next-generation sequencing software in mapping and assembly10.1038/jhg.2011.43 ↗
5. Basic local alignment search tool10.1016/S0022-2836(05)80360-2 ↗
6. Mapping short DNA sequencing reads and calling variants using mapping quality scores10.1101/gr.078212.108 ↗
7. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome10.1186/gb-2009-10-3-r25 ↗
8. Fast and accurate short read alignment with Burrows–Wheeler transform10.1093/bioinformatics/btp324 ↗
9. SOAP2: An improved ultrafast tool for short read alignment10.1093/bioinformatics/btp336 ↗
10. Li, H. (2013). Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. arXiv.
11. Ferragina, P., and Manzini, G. (2000, January 12–14). Opportunistic Data Structures with Applications. Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, Redondo Beach, CA, USA.
12. Lam, T.W., Li, R., Tam, A., Wong, S.C.K., Wu, E., and Yiu, S. (2009, January 1–4). High Throughput Short Read Alignment via Bi-directional BWT. Proceedings of the 2009 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2009, Washington, DC, USA.10.1109/BIBM.2009.42 ↗
13. Identification of Common Molecular Subsequences10.1016/0022-2836(81)90087-5 ↗
14. TopHat2: Accurate alignment of transcriptomes in the presence of insertions, deletions and gene fusions10.1186/gb-2013-14-4-r36 ↗
15. SOAP3: Ultra-fast GPU-based parallel alignment tool for short reads10.1093/bioinformatics/bts061 ↗
16. Luo, R., Wong, T., Zhu, J., Liu, C.M., Zhu, X., Wu, E., Lee, L.K., Lin, H., Zhu, W., and Cheung, D.W. (2013). Correction: SOAP3-dp: Fast, accurate and sensitive GPU-based short read aligner. PLoS ONE, 8.10.1371/annotation/823f3670-ed17-41ec-ba51-b50281651915 ↗
17. Klus, P., Lam, S., Lyberg, D., Cheung, M.S., Pullan, G., McFarlane, I., Yeo, G.S., and Lam, B.Y. (2012). BarraCUDA-a fast short read sequence aligner using graphics processing units. BMC Res. Notes, 5.10.1186/1756-0500-5-27 ↗
18. CUSHAW: A CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform10.1093/bioinformatics/bts276 ↗
19. CUSHAW2-GPU: Empowering Faster Gapped Short-Read Alignment Using GPU Computing10.1109/MDAT.2013.2284198 ↗
20. Long read alignment based on maximal exact match seeds10.1093/bioinformatics/bts414 ↗
21. Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences—Computer Science and Computational Biology, Cambridge University Press.10.1017/CBO9780511574931 ↗
22. An Extension of the String-to-String Correction Problem10.1145/321879.321880 ↗
23. Wagner, R.A. (1975, January 5–7). On the Complexity of the Extended String-to-String Correction Problem. Proceedings of the 7th Annual ACM Symposium on Theory of Computing, Albuquerque, NM, USA.10.1145/800116.803771 ↗
24. Efficient Algorithms for Approximate String Matching with Swaps10.1006/jcom.1998.0497 ↗
25. Parallel Computation for Extended Edit Distances Including Swap Operations
26. Genes for SMA: Multum in parvo10.1016/0092-8674(95)90442-5 ↗
27. Pattern Matching with Swaps10.1006/jagm.2000.1120 ↗
28. The Sequence Alignment/Map format and SAMtools10.1093/bioinformatics/btp352 ↗
29. The SAM/BAM Format Specification Working Group (2021, May 28). Sequence Alignment/Map Format Specification. Available online: https://samtools.github.io/hts-specs/SAMv1.pdf.
30. Roelofs, G., Gailly, J.L., and Adler, M. (2021, May 28). zlib. Available online: https://zlib.net/.
31. Deutsch, L.P., and Gailly, J.L. (2021, May 28). ZLIB Compressed Data Format Specification Version 3.3. Available online: https://datatracker.ietf.org/doc/html/rfc1950.
32. Deutsch, L.P. (2021, May 28). DEFLATE Compressed Data Format Specification Version 1.3. Available online: https://datatracker.ietf.org/doc/html/rfc1951.
33. Deutsch, L.P. (2021, May 28). GZIP File Format Specification Version 4.3. Available online: https://datatracker.ietf.org/doc/html/rfc1952.