5.315. stable_compatibility

DESCRIPTIONLINKSGRAPH
Origin

P.ย Flener, [BeldiceanuFlenerLorca06]

Constraint

๐šœ๐š๐šŠ๐š‹๐š•๐šŽ_๐šŒ๐š˜๐š–๐š™๐šŠ๐š๐š’๐š‹๐š’๐š•๐š’๐š๐šข(๐™ฝ๐™พ๐™ณ๐™ด๐š‚)

Argument
๐™ฝ๐™พ๐™ณ๐™ด๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š’๐š—๐š๐šŽ๐šก-๐š’๐š—๐š,๐š๐šŠ๐š๐š‘๐šŽ๐š›-๐š๐šŸ๐šŠ๐š›,๐š™๐š›๐šŽ๐šŒ-๐šœ๐š’๐š—๐š,๐š’๐š—๐šŒ-๐šœ๐š’๐š—๐š)
Restrictions
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐™ฝ๐™พ๐™ณ๐™ด๐š‚,[๐š’๐š—๐š๐šŽ๐šก,๐š๐šŠ๐š๐š‘๐šŽ๐š›,๐š™๐š›๐šŽ๐šŒ,๐š’๐š—๐šŒ])
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š’๐š—๐š๐šŽ๐šกโ‰ฅ1
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š’๐š—๐š๐šŽ๐šกโ‰ค|๐™ฝ๐™พ๐™ณ๐™ด๐š‚|
๐š๐š’๐šœ๐š๐š’๐š—๐šŒ๐š(๐™ฝ๐™พ๐™ณ๐™ด๐š‚,๐š’๐š—๐š๐šŽ๐šก)
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š๐šŠ๐š๐š‘๐šŽ๐š›โ‰ฅ1
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š๐šŠ๐š๐š‘๐šŽ๐š›โ‰ค|๐™ฝ๐™พ๐™ณ๐™ด๐š‚|
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š™๐š›๐šŽ๐šŒโ‰ฅ1
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š™๐š›๐šŽ๐šŒโ‰ค|๐™ฝ๐™พ๐™ณ๐™ด๐š‚|
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š’๐š—๐šŒโ‰ฅ1
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š’๐š—๐šŒโ‰ค|๐™ฝ๐™พ๐™ณ๐™ด๐š‚|
๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š’๐š—๐šŒ>๐™ฝ๐™พ๐™ณ๐™ด๐š‚.๐š’๐š—๐š๐šŽ๐šก
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
๐š’๐š—๐š๐šŽ๐šก-1๐š๐šŠ๐š๐š‘๐šŽ๐š›-4๐š™๐š›๐šŽ๐šŒ-{11,12}๐š’๐š—๐šŒ-โˆ…,๐š’๐š—๐š๐šŽ๐šก-2๐š๐šŠ๐š๐š‘๐šŽ๐š›-3๐š™๐š›๐šŽ๐šŒ-{8,9}๐š’๐š—๐šŒ-โˆ…,๐š’๐š—๐š๐šŽ๐šก-3๐š๐šŠ๐š๐š‘๐šŽ๐š›-4๐š™๐š›๐šŽ๐šŒ-{2,10}๐š’๐š—๐šŒ-โˆ…,๐š’๐š—๐š๐šŽ๐šก-4๐š๐šŠ๐š๐š‘๐šŽ๐š›-5๐š™๐š›๐šŽ๐šŒ-{1,3}๐š’๐š—๐šŒ-โˆ…,๐š’๐š—๐š๐šŽ๐šก-5๐š๐šŠ๐š๐š‘๐šŽ๐š›-7๐š™๐š›๐šŽ๐šŒ-{4,13}๐š’๐š—๐šŒ-โˆ…,๐š’๐š—๐š๐šŽ๐šก-6๐š๐šŠ๐š๐š‘๐šŽ๐š›-2๐š™๐š›๐šŽ๐šŒ-{8,14}๐š’๐š—๐šŒ-โˆ…,๐š’๐š—๐š๐šŽ๐šก-7๐š๐šŠ๐š๐š‘๐šŽ๐š›-7๐š™๐š›๐šŽ๐šŒ-{6,13}๐š’๐š—๐šŒ-โˆ…,๐š’๐š—๐š๐šŽ๐šก-8๐š๐šŠ๐š๐š‘๐šŽ๐š›-6๐š™๐š›๐šŽ๐šŒ-โˆ…๐š’๐š—๐šŒ-{9,10,11,12,13,14},๐š’๐š—๐š๐šŽ๐šก-9๐š๐šŠ๐š๐š‘๐šŽ๐š›-2๐š™๐š›๐šŽ๐šŒ-โˆ…๐š’๐š—๐šŒ-{10,11,12,13},๐š’๐š—๐š๐šŽ๐šก-10๐š๐šŠ๐š๐š‘๐šŽ๐š›-3๐š™๐š›๐šŽ๐šŒ-โˆ…๐š’๐š—๐šŒ-{11,12,13},๐š’๐š—๐š๐šŽ๐šก-11๐š๐šŠ๐š๐š‘๐šŽ๐š›-1๐š™๐š›๐šŽ๐šŒ-โˆ…๐š’๐š—๐šŒ-{12,13},๐š’๐š—๐š๐šŽ๐šก-12๐š๐šŠ๐š๐š‘๐šŽ๐š›-1๐š™๐š›๐šŽ๐šŒ-โˆ…๐š’๐š—๐šŒ-{13},๐š’๐š—๐š๐šŽ๐šก-13๐š๐šŠ๐š๐š‘๐šŽ๐š›-5๐š™๐š›๐šŽ๐šŒ-โˆ…๐š’๐š—๐šŒ-{14},๐š’๐š—๐š๐šŽ๐šก-14๐š๐šŠ๐š๐š‘๐šŽ๐š›-6๐š™๐š›๐šŽ๐šŒ-โˆ…๐š’๐š—๐šŒ-โˆ…

Figureย 5.315.1 shows the two trees we want to merge. Note that the leaves ๐šŠ and ๐š occur in both trees. Figureย 5.315.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.315.2 toย 5.315.9.

Figure 5.315.1. The two trees to merge
ctrs/stable_compatibility1
Figure 5.315.2. First solution corresponding to the ground instance of the example
ctrs/stable_compatibility2
Figure 5.315.3. Second solution
ctrs/stable_compatibility3
Figure 5.315.4. Third solution
ctrs/stable_compatibility4
Figure 5.315.5. Fourth solution
ctrs/stable_compatibility5
Figure 5.315.6. Fifth solution
ctrs/stable_compatibility6
Figure 5.315.7. Sixth solution
ctrs/stable_compatibility7
Figure 5.315.8. Seventh solution
ctrs/stable_compatibility8
Figure 5.315.9. Eighth solution
ctrs/stable_compatibility9
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.315.10. Supertree problem instance and two of its solutions
ctrs/stable_compatibility12
Figure 5.315.11. Three small phylogenetic trees
ctrs/stable_compatibility13

For example, the trees ๐’ฏ 1 and ๐’ฏ 2 of Figureย 5.315.10 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 b and g 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.315.11: ๐’ฏ 3 and ๐’ฏ 4 have ๐’ฏ 4 as a supertree under weak compatibility, as it suffices to contract the arc (3,2) to get ๐’ฏ 3 from ๐’ฏ 4 . However, ๐’ฏ 3 and ๐’ฏ 4 have no supertree under strong compatibility, as the most recent common ancestor of b and c, denoted by ๐‘š๐‘Ÿ๐‘๐‘Ž(b,c), is the same as ๐‘š๐‘Ÿ๐‘๐‘Ž(a,b) in ๐’ฏ 3 , namely 1, but not the same in ๐’ฏ 4 , as ๐‘š๐‘Ÿ๐‘๐‘Ž(b,c)=3 is an evolutionary descendant of ๐‘š๐‘Ÿ๐‘๐‘Ž(a,b)=2. Also, ๐’ฏ 4 and ๐’ฏ 5 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 O(l 2 ) time, where l 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

root concept: ๐š๐š›๐šŽ๐šŽ.

Keywords

application area: bioinformatics, phylogeny.

constraint type: graph constraint.

final graph structure: tree.

Arc input(s)

๐™ฝ๐™พ๐™ณ๐™ด๐š‚

Arc generator
๐ถ๐ฟ๐ผ๐‘„๐‘ˆ๐ธโ†ฆ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š—๐š˜๐š๐šŽ๐šœ1,๐š—๐š˜๐š๐šŽ๐šœ2)

Arc arity
Arc constraint(s)
๐š—๐š˜๐š๐šŽ๐šœ1.๐š๐šŠ๐š๐š‘๐šŽ๐š›=๐š—๐š˜๐š๐šŽ๐šœ2.๐š’๐š—๐š๐šŽ๐šก
Graph property(ies)
โ€ข ๐Œ๐€๐—_๐๐’๐‚๐‚โ‰ค1
โ€ข ๐๐‚๐‚=1
โ€ข ๐Œ๐€๐—_๐ˆ๐ƒโ‰ค2
โ€ข ๐๐€๐“๐‡_๐…๐‘๐Ž๐Œ_๐“๐Ž(๐š’๐š—๐š๐šŽ๐šก,๐š’๐š—๐š๐šŽ๐šก,๐š™๐š›๐šŽ๐šŒ)=1
โ€ข ๐๐€๐“๐‡_๐…๐‘๐Ž๐Œ_๐“๐Ž(๐š’๐š—๐š๐šŽ๐šก,๐š’๐š—๐š๐šŽ๐šก,๐š’๐š—๐šŒ)=0
โ€ข ๐๐€๐“๐‡_๐…๐‘๐Ž๐Œ_๐“๐Ž(๐š’๐š—๐š๐šŽ๐šก,๐š’๐š—๐šŒ,๐š’๐š—๐š๐šŽ๐šก)=0

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 ๐Œ๐€๐—_๐๐’๐‚๐‚โ‰ค1 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 one single vertex.

  • The second graph property ๐๐‚๐‚=1 imposes having only one single tree.

  • The third graph property ๐๐€๐“๐‡_๐…๐‘๐Ž๐Œ_๐“๐Ž(๐š’๐š—๐š๐šŽ๐šก,๐š’๐š—๐š๐šŽ๐šก,๐š™๐š›๐šŽ๐šŒ)=1 enforces for each vertex i a set of precedence constraints; for each vertex j of the precedence set there is a path from i to j in the final graph.

  • The fourth graph property ๐Œ๐€๐—_๐ˆ๐ƒโ‰ค2 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 ๐๐€๐“๐‡_๐…๐‘๐Ž๐Œ_๐“๐Ž(๐š’๐š—๐š๐šŽ๐šก,๐š’๐š—๐š๐šŽ๐šก, ๐š’๐š—๐šŒ)=0 and ๐๐€๐“๐‡_๐…๐‘๐Ž๐Œ_๐“๐Ž(๐š’๐š—๐š๐šŽ๐šก,๐š’๐š—๐šŒ, ๐š’๐š—๐š๐šŽ๐šก)=0 enforces for each vertex i a set of incomparability constraints; for each vertex j of the incomparability set there is neither a path from i to j, nor a path from j to i.

Figuresย 5.315.12 andย 5.315.13 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.315.2 shows the first solution satisfying all the precedence and incomparability constraints.

Figure 5.315.12. Precedence graph associated with the two trees to merge described by Figureย 5.315.1
ctrs/stable_compatibility10
Figure 5.315.13. Incomparability graph associated with the two trees to merge described by Figureย 5.315.1; the two cliques respectively correspond to the leaves of the two trees to merge.
ctrs/stable_compatibility11