In computational phylogenetics, tree alignment is a computational problem concerned with producing multiple sequence alignments, or alignments of three or more sequences of DNA, RNA, or protein. Sequences are arranged into a phylogenetic tree, modeling the evolutionary relationships between species or taxa. The edit distances between sequences are calculated for each of the tree's internal vertices, such that the sum of all edit distances within the tree is minimized. Tree alignment can be accomplished using one of several algorithms with various trade-offs between manageable tree size and computational effort.
Definition Input: A set S {\displaystyle S} of sequences, a phylogenetic tree T {\displaystyle T} leaf-labeled by S {\displaystyle S} and an edit distance function d {\displaystyle d} between sequences. Output: A labeling of the internal vertices of T {\displaystyle T} such that Σ e ∈ T d ( e ) {\displaystyle \Sigma _{e\in T}d(e)} is minimized, where d ( e ) {\displaystyle d(e)} is the edit distance between the endpoints of e {\displaystyle e} . The task is NP-hard.
Background
Sequence alignment
In bioinformatics, the basic method of information processing is to contrast the sequence data. Biologists use it to discover the function, structure, and evolutionary information in biological sequences. The following analyses are based on the sequence assembly: the phylogenetic analysis, the haplotype comparison, and the prediction of RNA structure. Therefore, the efficiency of sequence alignment will directly affect the efficacy of solving these problems. In order to design a rational and efficient sequence alignment, the algorithm derivation becomes an important branch of research in the field of bioinformatics. Generally, sequence alignment means constructing a string from two or more given strings with the greatest similarity by adding letters, deleting letters, or adding a space for each string. The multiple sequence alignment problem is generally based on pairwise sequence alignment and currently, for a pairwise sequence alignment problem, biologists can use a dynamic programming approach to obtain its optimal solution. However, the multiple sequence alignment problem is still one of the more challenging problems in bioinformatics. This is because finding the optimal solution for multiple sequence alignment has been proven as an NP-complete problem and only an approximate optimal solution can be obtained.
Distance matrix method Distance method measures the minimum operation number of character insertions, deletions, and substitutions that are required to transform one sequence u to the other sequence v when being operated on a pair of strings. The calculation of edit distance can be based on dynamic programming, and the equation is in O(|u|×|v|) time, where |u| and |v| are the lengths of u and v. The efficient estimation of edit distance is essential as Distance method is a basic principle in computational biology For functions of hereditary properties "symmetrization" can be used. Due to a series of functions being used to calculate edit distance, different functions may result in different results. Finding an optimal edit distance function is essential for the tree alignment problem.
The problem of tree alignment
Tree alignment results in a NP-hard problem, where scoring modes and alphabet sizes are restricted. It can be found as an algorithm, which is used to find the optimized solution. However, there is an exponential relationship between its efficiency and the number sequences, which means that when the length of the sequence is very large, the computation time required to get results is enormously long. Using star alignment to get the approximate optimized solution is faster than using tree alignment. However, whatever the degree of multiple-sequence similarity is, the time complexity of star alignment has a proportional relationship with the square of the sequence number and the square of the sequence average length. As usual, the sequence in MSA is so long that it is also inefficient or even unacceptable. Therefore, the challenge of reducing the time complexity to linear is one of the core issues in tree alignment.
Combinatorial optimization strategy Combinatorial optimization is a good strategy to solve MSA problems. The idea of combinatorial optimization strategy is to transform the multiple sequence alignment into pair sequence alignment to solve this problem. Depending on its transformation strategy, the combinatorial optimization strategy can be divided into the tree alignment algorithm and the star alignment algorithm. For a given multi-sequence set S {\displaystyle S} ={ s 1 {\displaystyle s_{1}} ,..., s n {\displaystyle s_{n}} }, find an evolutionary tree which has n leaf nodes and establishing one to one relationship between this evolutionary tree and the set S {\displaystyle S} . By assigning the sequence to the internal nodes of the evolutionary tree, we calculate the total score of each edge, and the sum of all edges' scores is the score of the evolutionary tree. The aim of tree alignment is to find an assigned sequence, which can obtain a maximum score, and get the final matching result from the evolutionary tree and its nodes' assigned sequence. Star alignment can be seen as a special case of the tree alignment. When we use star alignment, the evolutionary tree has only one internal node and n leaf nodes. The sequence, which is assigned to the internal node, is called the core sequence.
… excerpt ends here. Continue reading the full article.
