5.373. stable_compatibility
DESCRIPTION | LINKS | GRAPH |
- Origin
P.ย Flener, [BeldiceanuFlenerLorca06]
- Constraint
- Argument
- Restrictions
- Purpose
Enforce the construction of a stably compatible supertree that is compatible with several given trees. The notion of stable compatibility and its context are detailed in the Usage slot.
- Example
-
Figureย 5.373.1 shows the two trees we want to merge. Note that the leaves and occur in both trees.
Figure 5.373.1. The two trees to merge
The left part of Figureย 5.373.2 gives one way to merge the two previous trees. This solution corresponds to the ground instance provided by the example. Note that there exist 7 other ways to merge these two trees. They are respectively depicted by Figuresย 5.373.2 toย 5.373.5.
Figure 5.373.2. First solution (corresponding to the ground instance of the example) and second solution on how to merge the two trees and of Figureย 5.373.1
Figure 5.373.3. Third and fourth solutions on how to merge the two trees and of Figureย 5.373.1
Figure 5.373.4. Fifth and sixth solutions on how to merge the two trees and of Figureย 5.373.1
Figure 5.373.5. Seventh and eight solutions on how to merge the two trees and of Figureย 5.373.1
- Typical
- Symmetry
Items of are permutable.
- Usage
One objective of phylogeny is to construct the genealogy of the species, called the tree of life, whose leaves represent the contemporary species and whose internal nodes represent extinct species that are not necessarily named. An important problem in phylogeny is the construction of a supertreeย [BinindaEmondsGittlemanSteel02] that is compatible with several given trees. There are several definitions of tree compatibility in the literature:
A tree is strongly compatible with a tree if is topologically equivalent to a subtree that respects the node labelling.ย [NgWormald96]
A tree is weakly compatible with a tree if can be obtained from by a series of arc contractions.ย [Steel92]
A tree is stably compatible with a set of trees if is weakly compatible with each tree in and each internal node of can be labelled by at least one corresponding internal node of some tree in .
For the supertree problem, strong and weak compatibility coincide if and only if all the given trees are binaryย [NgWormald96]. The existence of solutions is not lost when restricting weak compatibility to stable compatibility.
Figure 5.373.6. Supertree problem instance and two of its solutions
Figure 5.373.7. Three small phylogenetic trees
For example, the trees and of Figureย 5.373.6 have and as supertrees under both weak and strong compatibility. As shown, all the internal nodes of can be labelled by corresponding internal nodes of the two given trees, but this is not the case for the father of and in . Hence and four other such supertrees are debatable because they speculate about the existence of extinct species that were not in any of the given trees. Consider also the three small trees in Figureย 5.373.7: and have as a supertree under weak compatibility, as it suffices to contract the arc to get from . However, and have no supertree under strong compatibility, as the most recent common ancestor of and , denoted by , is the same as in , namely 1, but not the same in , as is an evolutionary descendant of . Also, and have neither weakly nor strongly compatible supertrees.
Under strong compatibility, a first supertree algorithm was given inย [AhoSagivSzymanskiUllman81], with an application for database management systems; it takes time, where is the number of leaves in the given trees. Derived algorithms have emerged from phylogeny, for instance OneTreeย [NgWormald96]. The first constraint program was proposed inย [GentProsserSmithWei03], using standard, non-global constraints. Under weak compatibility, a phylogenetic supertree algorithm can be found inย [Steel92] for instance. Under stable compatibility, the algorithm from computational linguistics ofย [BodirskyKutz07] has supertree construction as special case.
- See also
- Keywords
application area: bioinformatics, phylogeny.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
To each distinct leave (i.e.,ย each species) of the trees to merge corresponds a vertex of the initial graph. To each internal vertex of the trees to merge corresponds also a vertex of the initial graph. Each vertex of the initial graph has the following attributes:
An index corresponding to a unique identifier.
A father corresponding to the father of the vertex in the final tree. Since the leaves of the trees to merge must remain leaves we remove the index value of all the leaves from all the father variables.
A set of precedence constraints corresponding to all the arcs of the trees to merge.
A set of incomparability constraints corresponding to the incomparable vertices of each tree to merge.
The arc constraint describes the fact that we link a vertex to its father variable. Finally we use the following six graph properties on our final graph:
The first graph property enforces the fact that the size of the largest strongly connected component does not exceed one. This avoid having circuits containing more than one vertex. In fact the root of the merged tree is a strongly connected component with a single vertex.
The second graph property imposes having only a single tree.
The third graph property enforces for each vertex a set of precedence constraints; for each vertex of the precedence set there is a path from to in the final graph.
The fourth graph property enforces that the number of predecessors (i.e.,ย arcs from a vertex to itself are not counted) of each vertex does not exceed 2 (i.e., the final graph is a binary tree).
The fifth and sixth graph properties and enforces for each vertex a set of incomparability constraints; for each vertex of the incomparability set there is neither a path from to , nor a path from to .
Figuresย 5.373.8 andย 5.373.9 respectively show the precedence and the incomparability graphs associated with the Example slot. As it contains too many arcs the initial graph is not shown. Figuresย 5.373.2 shows the first solution satisfying all the precedence and incomparability constraints.
Figure 5.373.8. Precedence graph associated with the two trees to merge described by Figureย 5.373.1
Figure 5.373.9. Incomparability graph associated with the two trees to merge described by Figureย 5.373.1; the two cliques respectively correspond to the leaves of the two trees to merge.