Fundamentals of Bioinformatics - Ogurtsov A.N. 2013

Methods of Bioinformatics Analysis
Phylogenetic Analysis
Cladistic Methods

According to the cladistic approach, groups are formed exclusively by species that share common derived traits—that is, features absent in their distant ancestors.

The cladistic approach is widely considered the optimal method for Phylogenetic Analysis because it aligns with and builds upon current evolutionary theory, operating on the premise that new species arise through the branching of evolutionary lineages (i.e., via cladogenesis).

A clade is defined as a monophyletic taxon.

A clade is a group of organisms or genes comprising a common ancestor and all its lineal descendants. The term "clade" originates from the Greek word κλάδος, meaning "branch," "twig," or "SHOOT." Occasionally, the feminine form "klada" is also encountered in the literature.

A taxon refers to a systematic group within biological Classification. A node represents the branching point of an evolutionary Lineage. In some cases, branch lengths correspond to the degree of divergence between species (Figure 65).

Class="center">

Figure 65 - Relationships among three mammals represented as a branch of a Phylogenetic Tree

Examples of cladograms in which the branching order reflects the evolutionary sequences of ancestral speciation are presented in Figures 21 and 22.

The cladistic approach evaluates potential evolutionary pathways, infers ancestral traits at all internal nodes, and selects the optimal tree based on a specific evolutionary model. The foundational premise of cladistics is that members of a given group, or clade, share a common evolutionary history and are more closely related to one another than to members of any other group.

This group is defined by specific shared characteristics that were absent in remote ancestors. Such shared derived traits can be any observable and describable features. Cladistic analysis is typically performed using either a set of phenotypic characters or a matrix of Base Pairs or amino acid residues within sequences.

Cladistics is based on three fundamental assumptions.

1. All organisms within any given group are related through common descent.

2. Evolutionary lineages periodically diverge.

3. Over time, descendants undergo characteristic changes.

Cladistic Methods deal exclusively with inheritance patterns derived from the analysis of potential taxon trees. They aim to select the correct tree and employ detailed models of Evolutionary Processes.

The most popular cladistic methods are:

1) molecular phylogenetics method — Maximum Parsimony;

2) Maximum Likelihood method.

These methods focus on sequence data and begin with Multiple Sequence Alignment. Neither method relies on organismal Anatomical Features, such as the average weight of an adult individual.

The Maximum Parsimony method (also known as the minimum evolution method), proposed by W. Fitch, predicts the evolutionary tree that minimizes the number of steps required to account for the observed sequence variation.

To predict with the highest probability which sequence positions share identical characters (sequence elements), a multiple sequence alignment must be constructed. Such aligned positions will form vertical columns of matching sequence elements. For each aligned position, phylogenetic trees requiring the minimum number of evolutionary changes to produce the observed sequence variations are identified. This analysis is performed for every position in the sequence alignment. Finally, the trees that yield the fewest overall changes across all sequence positions are determined.

The maximum parsimony method is used to construct trees based on the minimum number of Mutations required to transform one sequence into another.

For example, suppose we are given species with homologous sequences ATCG, ATGG, TTCA, TCGA (Figure 66).

Figure 66 — Two genealogical trees of mutations

The tree presented in Figure 66(a) posits 4 mutations. The alternative tree shown in Figure 66(b) posits 7 mutations. Note that the second tree implies that the G→A Substitution at the fourth position occurs independently twice.

Tree (a) is optimal according to the maximum parsimony method, as no other tree yields fewer mutations.

In many cases, several trees may yield the same number of mutations, which is fewer than other trees. In such cases, the maximum parsimony method does not provide a unique answer.

Software for constructing phylogenetic trees—the PHYLIP (PHYLogeny Inference Package) software suite—consists of 35 programs that lack a graphical interface:

http://cmgm.stanford.edu/phylip/;

http://evolution.genetics.washington.edu/phylip.html.

Input data are provided in PHYLIP's native format. The outtree file containing the tree is presented in the universal Newick tree format (also known as Newick notation or New Hampshire tree format).

The core maximum parsimony analysis tools included in the PHYLIP package are DNAPARS, DNAPENNY, DNACOMP, DNAMOVE, and PROTPARS.

The Maximum Likelihood method, based on probabilistic calculations, identifies the tree that best describes the changes observed in a set of sequences. This method is similar to maximum parsimony in that the analysis is performed for each Column of a multiple sequence alignment, taking into account all possible trees.

For each constructed tree, the number of probable changes, or mutations, that caused the observed sequence variations is estimated. Since The rate of novel mutations is very low, the more mutations required to reconcile a given tree with the available data, the less likely that tree is. For each tree topology, the evolutionary rate varies and parameters are optimized to maximize the probability of generating the observed sequences.

Trees with the fewest changes are the most likely.

The maximum likelihood method makes it possible to construct an expected model of sequence change and to weigh the probabilities of substitution of any residue for any other across all positions. The PHYLIP package includes two programs—DNAML and DNAMLK—designed for phylogenetic analysis using the maximum likelihood method.

The variable evolutionary rate problem. Suppose that four species A, B, C, and D share the phylogenetic tree shown in Figure 67(a). This tree corresponds to the distance matrix presented in Figure 68(a).

Assume that species D evolves very rapidly, while the tree topology remains unchanged. In this case, we observe the distance matrix shown in Figure 68(b). An incorrect phylogenetic tree, shown in Figure 67(b), corresponds to this matrix.

Figure 67 - Two phylogenetic trees of mutations

All the methods discussed above are susceptible to errors of this type if the evolutionary rate varies drastically across different Branches of the tree.

Figure 68 - Distance matrices corresponding to the phylogenetic trees in Figure 67

To check for such variations, one should consider an outgroup—species that are known to be more distant from all the species for which the tree is being constructed.

For instance, if the evolutionary rate in primates is constant, we expect to see approximately equal distances between primates and, say, a cow. If this is not the case, the assumption of a constant evolutionary rate in primates is invalid.

Computational analysis. Cladistic methods (maximum parsimony and maximum likelihood) are more accurate than simple clustering methods such as UPGMA, but they require significantly more computational resources to solve practical problems.

The total number of possible trees that must be evaluated by cladistic methods grows extremely rapidly as the number of species increases. Consequently, in many interesting cases, these methods can only yield an approximate solution, even under significant assumptions.

Since phylogenetic inference is often approximate, It is important to validate the results. Validation methods include:

1. Comparing phylogenies derived from different taxonomic characteristics. Are they consistent? If trees derived from different characteristics share consistent subtrees, they are likely correct, whereas inconsistent subtrees are incorrect.

2. The analysis of taxon subsets can yield the same answer with respect to a subset—a subtree constructed from a subset must be consistent with the full tree.

3. Formal statistical tests involving recalculation on a subset of the original data. These methods are known as jackknife and bootstrap.

4. If a tree has very long branches, there are strong reasons to assume rate heterogeneity in evolution, in which case The Use of an outgroup is required.

Jackknife performs calculations on a random subset of data. To reconstruct a phylogeny from multiple sequence alignment, random sets of alignment positions are selected and calculations are performed independently for them. If identical subtrees are recovered, the tree is considered reliable, and unreliable otherwise.

Bootstrap works similarly, except that randomly selected positions may appear in the sample multiple times so that the Sample size matches the original dataset.