Tree alignment

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

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.[2]

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.[3] The efficient estimation of edit distance is essential as Distance method is a basic principle in computational biology[4] 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.

When the combinatorial optimization strategy is used 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 the Aho-Corasick search algorithm is an efficient approach to solve the pairwise sequence alignment problem. The aim of combining the keyword tree theory and the Aho-Corasick search algorithm is to solve this kind of problem: for a given long string ${\displaystyle T}$ and a set of short strings ${\displaystyle P}$={${\displaystyle p_{1}}$,${\displaystyle p_{2}}$,... ,${\displaystyle p_{z}}$} (z∈N,z>1), find the location of all ${\displaystyle P_{i}}$ in ${\displaystyle T}$. The keyword tree produced by set ${\displaystyle P}$ is used, and then searched for in ${\displaystyle T}$ with this keyword tree through the Aho-Corasick search algorithm.[6] The total time complexity of using this method to find all ${\displaystyle P_{i}}$'s location in the T is O(${\displaystyle m}$+${\displaystyle n}$+${\displaystyle k}$), where ${\displaystyle m}$=|${\displaystyle T}$| (the length of ${\displaystyle T}$), ${\displaystyle n}$=Σ|${\displaystyle P_{i}}$| (the sum of all ${\displaystyle P_{i}}$'s lengths) and ${\displaystyle k}$ means the sum of occurrence for all ${\displaystyle P_{i}}$ in ${\displaystyle T}$.

The keyword tree of the set ${\displaystyle P}$={${\displaystyle p_{1}}$,${\displaystyle p_{2}}$,... ,${\displaystyle 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 ${\displaystyle P_{i}}$ (i=1,2,...,z) corresponds to a node ${\displaystyle v}$, and the path from the root K to the node ${\displaystyle v}$ can exactly correctly spell the string ${\displaystyle P_{i}}$.

For each leaf node of this K tree, it corresponds to one of the certain patterns of set ${\displaystyle P}$.

${\displaystyle L(v)}$ is used to represent the STRING which is connected from the root node to the node ${\displaystyle v}$. ${\displaystyle Lp(v)}$ will then be used to represent the length of the longest suffix (also, this suffix is the prefix of one of patterns in the set ${\displaystyle P}$). Searching this prefix from the root node in the keyword tree, and the last node denoted by ${\displaystyle n_{v}}$ when the search is over.[7]

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

Establishing a failure link is the key to improve the time complexity of the Aho-Corasick algorithm. It can be used to reduce the original polynomial time to the linear time for searching. Therefore, the core of keyword tree theory is to find all failure links (which also means finding all ${\displaystyle n_{v}}$s) of a keyword tree in the linear time. It is assumed that every ${\displaystyle n_{v}}$ of all nodes ${\displaystyle v}$, whose distance from the root node is less than or equal ${\displaystyle k}$, can be found. The ${\displaystyle n_{v}}$ of the node ${\displaystyle v}$ whose distance from the root node is ${\displaystyle k}$ + 1 can then be sought for. Its parent node is ${\displaystyle v'}$, and the letter represented by the node ${\displaystyle v}$ and ${\displaystyle v'}$, is ${\displaystyle x}$.

(1): If the next letter of the node ${\displaystyle n_{v}'}$ is ${\displaystyle x}$, the other node of this edge can be set as ${\displaystyle w}$, and ${\displaystyle n_{v}}$=${\displaystyle w}$.

(2): If all letters are not ${\displaystyle x}$ by searching all edges between ${\displaystyle n_{v}'}$ and its child nodes, ${\displaystyle L(n_{v})}$ is a suffix of ${\displaystyle L(n_{v}')}$ plus ${\displaystyle x}$. Because this suffix matches the STRING beginning with the root node (similar to prefix), the ${\displaystyle x}$ after ${\displaystyle n_{v}'}$ can be detected or not. If not, this process can be continued until ${\displaystyle x}$ or the root node is found.

After establishing all failure links in the keyword tree, the Aho-Corasick search algorithm is used to find the locations of all ${\displaystyle P_{i}}$ (i=1,2,...,z) in the linear time. In this step, the time complexity is O(m+k).

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

Roughly, tree alignment graph aims to align trees into a graph and finally synthesize them to develop statistics. In biology, tree alignment graphs (TAGs) are used to remove the evolutionary conflicts or overlapping taxa from sets of trees and can then be queried to explore uncertainty and conflict. By integrating methods of aligning, synthesizing and analyzing, the TAG aims to solve the conflicting relationships and partial overlapping taxon sets obtained from a wide range of sequences. Also, the tree alignment graph serves as a fundamental approach for supertree and grafting exercises, which have been successfully tested to construct supertrees by Berry.[10] Because the transformation from trees to a graph contain similar nodes and edges from their source trees, TAGs can also 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]