Tree rearrangement

Tree rearrangement

Tree rearrangements are used in heuristic algorithms devoted to searching for an optimal tree structure. They can be applied to any set of data that are naturally arranged into a tree, but have most applications in computational phylogenetics, especially in maximum parsimony and maximum likelihood searches of phylogenetic trees, which seek to identify one among many possible trees that best explains the evolutionary history of a particular gene or species.

Basic tree rearrangements

The simplest tree-rearrangement, known as nearest-neighbor interchange, exchanges the connectivity of four subtrees within the main tree. Because there are three possible ways of connecting four subtrees,[1] and one is the original connectivity, each interchange creates two new trees. Exhaustively searching the possible nearest-neighbors for each possible set of subtrees is the slowest but most optimizing way of performing this search. An alternative, more wide-ranging search, subtree pruning and regrafting (SPR), selects and removes a subtree from the main tree and reinserts it elsewhere on the main tree to create a new node. Finally, tree bisection and reconnection (TBR) detaches a subtree from the main tree at an interior node and then attempts all possible connections between branches of the two trees thus created. The increasing complexity of the tree rearrangement technique correlates with increasing computational time required for the search, although not necessarily with their performance.[2]

Tree fusion

The simplest type of tree fusion begins with two trees already identified as near-optimal; thus, they most likely have the majority of their nodes correct but may fail to resolve individual tree "leaves" properly; for example, the separation ((A,B),(C,D)) at a branch tip versus ((A,C),(B,D)) may be unresolved.[1] Tree fusion swaps these two solutions between two otherwise near-optimal trees. Variants of the method use standard genetic algorithms with a defined objective function to swap high-scoring subtrees into main trees that are high-scoring overall.[3]

References

  1. ^ a b Felsenstein J. (2004). Inferring Phylogenies Sinauer Associates: Sunderland, MA.
  2. ^ Takahashi K, Nei M. (2000). Efficiencies of fast algorithms of phylogenetic inference under the criteria of maximum parsimony, minimum evolution, and maximum likelihood when a large number of sequences are used. Mol Biol Evol 17(8):1251-8.
  3. ^ Matsuda H. (1996). Protein phylogenetic inference using maximum likelihood with a genetic algorithm. Pacific Symposium on Biocomputing 1996, pp512-23.

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • B-tree — In computer science, a B tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time. It is most commonly used in databases and filesystems. In B trees, internal (non leaf)… …   Wikipedia

  • Computational phylogenetics — is the application of computational algorithms, methods and programs to phylogenetic analyses. The goal is to assemble a phylogenetic tree representing a hypothesis about the evolutionary ancestry of a set of genes, species, or other taxa. For… …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Category:Optimization algorithms — An optimization algorithm is an algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x. Here, x can be a scalar or vector of continuous or discrete values …   Wikipedia

  • Y-chromosomal Adam — Y chromosome in descendants of one human male In human genetics, Y chromosomal Adam ( Y MRCA) is the theoretical most recent common ancestor (MRCA) from whom all living people are descended patrilineally (tracing back along the paternal lines of… …   Wikipedia

  • Enfilade (Xanadu) — Enfilades are a class of tree data structures used in Project Xanadu designs of the 1970s and 1980s. Enfilades allow quick editing, versioning, retrieval and inter comparison operations in a large, cross linked hypertext database. The Xanadu Gold …   Wikipedia

  • Imperial Crypt Vaults — The Imperial Crypt Vaults are the various chambers of the Imperial Crypt in Vienna in which most members of the senior lines of the Habsburg dynasty, the hereditary Emperors of the Holy Roman Empire, have been entombed, beginning in 1632.The… …   Wikipedia

  • Multiple sequence alignment — A multiple sequence alignment (MSA) is a sequence alignment of three or more biological sequences, generally protein, DNA, or RNA. In many cases, the input set of query sequences are assumed to have an evolutionary relationship by which they… …   Wikipedia

  • Magical Starsign — Front cover of the U.S. Magical Starsign package. Developer(s) Brownie Brown …   Wikipedia

  • Comitium — The Forum Romanum and the comitium (behind fencing) after 44 BC and the rearrangement of Julius Caesar Location Regione VIII Forum Romanum …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”