The Research On Algorithms For The Longest Common Subsequence Problem And Variants

Sequence comparison is an important topic in bioinformatics,it's used to find the similarity of sequences.The longest common subsequence problem and its variants are significant and fundamental in sequence comparison.The need of applications of multiple sequences ,such as multiple sequence alignment,has quickly increased since 2000.This thesis mainly completes tasks as follows:1.We propose two approximating algorithms LALCS and RALCS for LCS problem of three input strings.Even if the approximation factors of the two algorithms are still 1Σ,the time complexities of the two improved algorithms are O ( n )and O ( nlogn ),the space complexities are O ( n )and O ( nlogn ),respectively.they can both get much better results in comparison of Gotthilf's approximating LCS algorithm in most cases,experimental results have proven the validity of the two algorithms.2.Two improved CLCS algorithms are put forward to solve the constrained longest common subsequence problem of multiple sequences,they make use of the two novel algorithms LALCS and RALCS,we can receive better definition in comparison of the basic approximating CLCS algorithm by experiments.3.Two conditions to slove the constrained sequence alignment problem are demonstrated theoretically when the penalty factor ? in the distance function is 0.Two algorithms for the longest common subsequence problem is extended to solve CSA problem . The time complexities of the two improved algorithms are O ( nmr )and O ( nmr ),the space complexities are O ( nmr )and O (( n+m ) r ),respectively.The results of the two algorithms are exact without mismatchs.Experiments prove the validity of the two algorithms.