A Biological Multiple Sequence Alignment Tool Based On Heuristic Approach

Biological sequences refer to DNA sequences or amino acid sequences of proteins.Multiple sequence alignment refers to the alignment of more than three biological sequences of similar length.The so-called sequence alignment refers to the alignment arrangement with the optimal similarity of two sequences.Due to the development of biochemical technologies such as high-throughput sequencing,the mass of biological sequences has been increasing.Multi-sequence alignment is more and more widely used in the field of biology.Because multi-sequence alignment problem has been proved to be a NP hard problem,various heuristic methods are often used to produce approximate solution of space-time balance in practice.Blast is one of the most popular software systems that enables multiple sequence alignment.This paper studies and improves the core algorithm based on Blast algorithm.This paper studies and introduces many typical algorithms for sequence alignment problems,especially the most popular BLAST and 2 hit BLAST algorithm.To improve the time consumption of BLAST algorithm and the accuracy of 2 hit BLAST algorithm,an improved algorithm of 2.5 hit BLAST is proposed to achieve better balance of time consumption and accuracy.After the design of 2.5 hit BLAST algorithm is introduced in detail,a DNA multi-sequence alignment system is designed and implemented with this algorithm as the core,and the feasibility of this algorithm is verified,which provides an additional useful choice for biological multiple sequence alignment.