Tree alignment

In computational phylogenetics, tree alignment is the problem of producing a multiple sequence alignment,which can be used to analyse a set of sequences with evolutionary relationship using a fixed tree. Essentially,tree alignment is an algorithm for optimizing phylogenetic tree by calculating the edit distance to achieve the minimum value.To be specific, phylogenetic tree shows an evolutionary relationship between different species and taxa joined together are assumed to have the same ancestor.

Formally, tree alignment is the following optimization problem.

Input: A set $S$ of sequences, a phylogenetic tree $T$ leaf-labeled by $S$ and an edit distance function $d$ between sequences,

Output: A labeling of the internal vertices of $T$ such that $\Sigma_{e \in T} d(e)$ is minimized, where $d(e)$ is the edit distance between the endpoints of $e$.

The task is NP-hard^[1]

Background

Sequence alignment

This is a simple Sequence Alignment of Insulin gene between rat, human and chicken. The labeled nucleotides are the different nucleotides with rat Ⅰ and --- means the missing nucleotides

In bioinformatics, the basic method of information processing is to contrast the sequence data. It has a very important significance when biologists use it to discover the function, structure and evolutionary information in biological sequences. From the sequence assembly, the phylogenetic analysis, the haplotype comparison, and the prediction of RNA structure are all based on sequence alignment, so the efficiency of sequence alignment, especially multiple sequence alignment, will directly affect the effect of these problems’ solution. Therefore, to design a rational and efficient sequence alignment algorithm becomes a very 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, deleting letters, or adding a space for each string. The multiple sequence alignment problem is generally based on pairwise sequence alignment and currently, for pairwise sequence alignment problem, biologists can use dynamic programming approach to obtain its optimal solution. However, the multiple sequence alignment problem is still one of the intractable problems in bioinformatics, because finding the optimal solution of multiple sequence alignment has been proved as a NP-complete problem so that only approximate optimal solution can be obtained.^[2]

Edit distance

Edit distance 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^[3] Edit distance are the basic principle in computational biology, thus an efficient estimation of edit distance is very essential .^[4] There are some functions to calculate edit distance, including “symmetrization” used for functions of hereditary properties. Because there are a series of functions being used to calculate edit distance, different functions may result in distinct results. Finding an optimal edit distance function seems essential for further explanation.

The problem of Tree alignment

This figure indicates the growth rate about the exponential time, the polynomial time and the linear time

Tree alignment problem is a NP-hard problem when we restrict its scoring mode and alphabet size, and it can be found an algorithm, which uses to find the optimized solution. However, there is an exponential relationship between its efficiency and the number of sequence, it means when the number of sequence is very large, the runtime before getting results is an enormous figure and it is unacceptable. Using star alignment is faster than tree alignment to get the approximate optimized solution. However, whatever the degree of multiple-sequence similarity is, the time complexity of star alignment has a proportional relationship with the square of sequence number and the square of the sequence average length. In usual, the sequence in MSA is so long that it is also inefficient or even unacceptable. Therefore, how to reduce the time complexity to linear is one of the core issues in the Tree alignment.

Combinatorial Optimization Strategy

Combinatorial optimization is a good strategy to solve MSA problem. 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 sequences set $S$ ={$s_1$,…,$s_n$ }, finding an evolutionary tree which has n leaf nodes and establishing one to one relationship between this evolutionary tree and the set 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’ score 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 by 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 core sequence.^[5]

The Keyword Tree Theory and Aho-Corasick search algorithm

When we use combinatorial optimization strategy to transform the multiple sequence alignment into pair sequence alignment, the main problem is changed from how to improve the efficiency of multiple sequence alignment to how to improve the efficiency of pairwise sequence alignment. The Keyword Tree Theory and Aho-Corasick search algorithm is an efficient approach to solve the pairwise sequence alignment problem. The aim of combining the keyword tree theory and Aho-Corasick search algorithm is to solve this kind of problem: for a given long string T and a short strings set $P$={$p_1$,$p_2$,… ,$p_z$} (z∈N,z>1), find the location of all $P_i$ in the T. We use keyword tree produced by set $P$, and then search in the T with this keyword tree by Aho-Corasick search algorithm.^[6] The total time complexity of using this method to find all $P_i$’s location in the T is O(m+n+k), where m=|T| (the length of T), n=∑|$P_i$| (the sum of all $P_i$’s length) and k means the sum of occurrence for all $P_i$ in the T.

Keyword Tree Theory

The keyword tree of the set $P$={$p_1$,$p_2$,… ,$p_z$ } (z∈N,z>1) is a rooted tree, whose root denoted by K, and this keyword tree satisfies: (1): Each edge clearly demarcates one letter. (2): Any two edges separated from the same node are to correspond to different letters. (3) Each pattern $P_i$ (i=1,2,…,z) corresponds to a node $v$, and the path from the root K to the node $v$ can exactly correctly spell the string $P_i$. For each leaf node of this K tree, it corresponds to one of certain patterns of set $P$.

And We use $L(v)$ to represent the STRING which is connected from the root node to the node $v$. We also use $Lp(v)$ to represent the length of the longest suffix(also, this suffix is the prefix of one of patterns in the set $P$). Searching this prefix from the root node in the keyword tree, and the last node denoted by $n_v$ when the search is over. When $Lp(v)$=0, $n_v$ =K. The ordered pair ($v$, $n_v$) called a failure link.^[7]

For example, The set $P$={potato, tattoo, theater, other}, and the keyword tree is shown on the right. Obviously, in that example if $L(v)$=potat, then $Lp(v)$=|tat|=3, and the failure link of the node $v$ is shown in that figure.

To establish failure link is the key to improve the time complexity of Aho-Corasick algorithm. It can reduced the original polynomial time to the linear time for searching. Therefore, the core of keyword tree theory is to find all failure links(also means find all $n_v$) of a keyword tree in the linear time. We assume that we find every $n_v$ of all nodes $v$ whose distance from the root node is less than or equal k, and now we are seeking the $n_v$ of the node $v$ whose distance from the root node is k +1. Its parent node is $v'$, and the letter represented by the node $v$ and $v'$, is x. (1): If the next letter of the node $n_v'$ is x, we set the other node of this edge as $w$, and $n_v$=$w$. (2): If all letters is not x by searching all edges between $n_v'$ and its child nodes, $L(n_v)$ is a suffix of $L(n_v' )$ plus x. Because this suffix matches the STRING begin with the root node (similar to prefix), we can detect if there is x after $n_v'$ or not. And if not, continue this process until find x or find the root node.

Aho-Corasick search algorithm

After establishing all failure links in the keyword tree, we use Aho-Corasick search algorithm to find the locations of all $P_i$ (i=1,2,…,z) in the linear time. In this step, the time complexity is O(m+k).

Other strategies

In MSA ,DNA,RNA, and proteins sequences are usually generated and they are assumed to have evolutionary relationship .By comparing generated maps of RNA,DNA and sequences from evolutionary family ,people can assess conservation of protein ,find functional gene domains by comparing differences between evolutionary sequences. Generally ,heuristic algorithm and tree alignment graph are also adopted to solve multiple sequence alignment problems.

Heuristic Algorithm

Generally heuristic algorithm relies on the iterative strategy, scilicet based on a comparison method, optimizing the results of multiple sequence alignment by the iterative process. Davie M proposed using particle swarm optimization algorithm to solve the multiple sequence alignment problem; Ikeda T proposed a heuristic algorithm which is based on A* search algorithm; Bimey E first proposed using hidden Markov model to solve the multiple sequence alignment problem; and many other biologists use genetic algorithm to solve it.^[8][9] All these algorithms generally are robust and insensitive to the number of sequences, but they also have shortcoming, for example, the result got from particle swarm optimization algorithm is unstable and its merits depend on the selection of random numbers, the runtime of A * search algorithm is too long and the genetic algorithm is easy to fall into local excellent.

Tree Alignment Graph

Roughly ,tree alignment graph aims to align trees into a graph and finally synthesis them to develop statistics.For biologist,tree alignment graph (TAGs) are used to remove the evolutionary conflicts or overlapping taxa from sets of trees and can be queried to explore uncertainty and conflict.By integrating methods of aligning ,synthsizing and analyzing ,the TAG aims to solve the conflicting relationships and partial overlapping taxon sets obtained from a wide range of sequence.Also ,tree alignment graph serves as a fundamental approach for supertree and grafting exercise,which have been successfully tested to construct supertrees by Berry et al.^[10] Because the transformation from trees to a graph contain similar nodes and edges from their source trees ,TAGs also can provide extraction of original source trees for further analysis . TAG is a combination of a set of aligning trees,it can store conflicting hypotheses evolutionary relationship and synthesize the source trees to develop evolutionary hypotheses ,therefore ,it is a basic method to solve other alignment problems.^[11]

See also

• Generalized tree alignment

References

1. Elias, Isaac (2006), "Settling the intractability of multiple alignment", J Comput Biol 13 (7): 1323–1339, doi:10.1089/cmb.2006.13.1323, PMID 17037961
2. L Wang,T Jiang. On the complexity of multiple sequence alignment[J]. Journal of Computational Biology, 194,1(4):337— 34.
3. Yen Hung Chen, On the bottleneck tree alignment problems, INFORMATION SCIENCES; JUN 1, 2010; 180; 11; p2134-p2141
4. Ostrovsky,Rafail ;Rabani,Yuval. Journal of the ACM. Oct 2007, Vol.54 Issue 5, p1-16. 16p. DOI: 10.1145/1284320.1284322.
5. Serafim Batzoglou. The many faces of sequence alignment[J]. Briefings in Bioinformatics. 2005,6(1):6—22
6. Aho A V, Corasick M J. Efficient string matching: an aid to bibliographic search[J]. Communications of ACM, 1975,18(6): 333—340.
7. D Gusfield. Algorithms on strings, trees and sequences: computer science and computational biology[M]. Cambridge: Cambridge University Press.1997.
8. RobertC Edgar,Serafim Batzoglou. Multiple sequence alignment[J]. Current opinion in structural biology. 2006,16(3):368— 373.
9. Notredame C, Higgins D.G. SAGA:sequence alignment by genetic algorithm [J]. Nucleic Acids Research. 1996,24(8):1515-1524.
10. Wilkinson M,Pisani D ,Measuring support and finding unsupported relationships in supertrees ,Systematic Biology 54:823-831.
11. Stephen A.Smith,Joseph W.Brown,analyzing and synthesizing phylogenies using tree alignment graphs,PLoS Computational Biology 9(9).