Parallel Computation Method for Multi-sequence Alignment of Biological Genes Based on Keyword Tree
XU Shengchao
Abstract：In response to the square level time complexity problem of traditional star alignment algorithms in bioinformatics multi sequence alignment,a keyword tree algorithm is introduced to improve the star alignment algorithm.The biological informa-tion sequences are segmented and keyword trees for each subsequence are generated.The sliding window method is used to search for the sequence with the most perfectly matched base pairs with other sequences in the keyword tree of the sequence,and this se-quence is set as the central sequence,the central sequence is compared with other sequences to obtain the final multi sequence alignment result,and parallelized the improved star alignment algorithm is parallelied using Apache Hadoop Yarn to improve the speed of bioinformatics multi sequence alignment.Through experiments,it can be seen that the improved star alignment algorithm can significantly improve the speed of alignment during runtime,and Apache Hadoop Yarn parallelism results are excellent.On top of the improved star alignment algorithm,the sequence alignment time is further reduced through parallelization processing.
Keywords：keyword treestar comparison algorithmbioinformaticsbase pairmmultithreading
Publication Date：2025-07-20
Online Publishing Date：2025-09-25(First online date of this platform, not the publication date of the document)
Pages：6( 1789-1793,1799 )