作者：
Haojing ShaoJue RuanShenzhen Branch
Guangdong Laboratory of Lingnan Modern AgricultureGenome Analysis Laboratory of the Ministry of Agriculture and Rural AffairsAgricultural Genomics Institute at ShenzhenChinese Academy of Agricultural SciencesShenzhen 518120China
Increasing the accuracy of the nucleotide sequence alignment is an essential issue in genomics *** classic dynamicprogramming(DP)algorithms(e.g.,Smith–Waterman and Needleman–Wunsch)guarantee to produce the optimal ...
详细信息
Increasing the accuracy of the nucleotide sequence alignment is an essential issue in genomics *** classic dynamicprogramming(DP)algorithms(e.g.,Smith–Waterman and Needleman–Wunsch)guarantee to produce the optimal result,their time complexity hinders the application of large-scale sequence *** optimization efforts that aim to accelerate the alignment process generally come from three perspectives:redesigning data structures[e.g.,diagonal or striped Single Instruction Multiple Data(SIMD)implementations],increasing the number of parallelisms in SIMD operations(e.g.,difference recurrence relation),or reducing search space(e.g.,banded DP).However,no methods combine all these three aspects to build an ultra-fast *** this study,we developed a banded Striped Aligner(BSAlign)library that delivers accurate alignment results at an ultra-fast speed by knitting a series of novel methods together to take advantage of all of the aforementioned three perspectives with highlights such as active F-loop in striped vectorization and striped move in banded *** applied our new acceleration design on both regular and edit distance pairwise *** achieved 2-fold speed-up than other SIMD-based implementations for regular pairwise alignment,and 1.5-fold to 4-fold speed-up in edit distance-based implementations for long *** is implemented in C programing language and is available at https://***/ruanjue/bsalign.
Independent scoring of the aligned sections to determine the quality of biological sequence alignments enables recursive definitions of the overall alignment score. This property is not only biologically meaningful bu...
详细信息
Independent scoring of the aligned sections to determine the quality of biological sequence alignments enables recursive definitions of the overall alignment score. This property is not only biologically meaningful but it also provides the opportunity to find the optimal alignments using dynamicprogramming-based algorithms. dynamicprogramming is an efficient problem solving technique for a class of problems that can be solved by dividing into overlapping subproblems. Pairwise sequence alignment techniques such as Needleman–Wunsch and Smith–Waterman algorithms are applications of dynamicprogramming on pairwise sequence alignment problems. These algorithms offer polynomial time and space solutions. In this chapter, we introduce the basic dynamicprogramming solutions for global, semi-global, and local alignment problems. Algorithmic improvements offering quadratic-time and linear-space programs and approximate solutions with space-reduction and seeding heuristics are discussed. We finally introduce the application of these techniques on multiple sequence alignment briefly. less
暂无评论