Maximum Agreement Subtree Problem
   HOME

TheInfoList



Click Here for Items Related To - Maximum Agreement Subtree Problem
OR:
Maximum Agreement Subtree Problem on:   [Wikipedia]   [Google]   [Amazon]

The maximum agreement subtree problem is any of several closely related problems in
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
and
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
. In all of these problems one is given a collection of
trees In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...
T_1,\ldots, T_m each containing n leaves. The leaves of these trees are given labels from some set L with , L, =n so that no pair of leaves in the same tree sharing the same label, within the same tree the labelling for each leaf is distinct. In this problem one would like to find the largest subset L'\subset L such that the minimal spanning subtrees containing the leaves in L', of T_1\mid S,\ldots, T_m\mid S are the "same" while preserving the labelling.


Formulations


Maximum homeomorphic agreement subtree

Source: This version requires that the subtrees T_1\mid S,\ldots, T_m\mid S are
homeomorphic In mathematics and more specifically in topology, a homeomorphism ( from Greek roots meaning "similar shape", named by Henri Poincaré), also called topological isomorphism, or bicontinuous function, is a bijective and continuous function betw ...
to one another.


Rooted maximum homeomorphic agreement subtree

This version is the same as the ''maximum homeomorphic agreement subtree'', but we further assume that T_1,\ldots,T_m are rooted and that the subtrees T_1\mid S,\ldots, T_m\mid S contain the root node. This version of the maximum agreement subtree problem is used for the study of
phylogenetic trees A phylogenetic tree or phylogeny is a graphical representation which shows the evolutionary history between a set of species or taxa during a specific time.Felsenstein J. (2004). ''Inferring Phylogenies'' Sinauer Associates: Sunderland, MA. In o ...
. Because of its close ties with phylogeny this formulation is often what is mean when one refers to the "maximum agreement subtree" problem.


Other variants

There exits other formulations for example the ''(rooted) maximum isomorphic agreement subtree'' where we require the subtrees to be
isomorphic In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
to one another.


See also

* Frequent subtree mining


References

* {{cite journal, last1=Kao, first1=Ming-Yang, last2=Lam, first2=Tak-Wah, last3=Sung, first3=Wing-Kin, last4=Ting, first4=Hing-Fung, title=An Even Faster and More Unifying Algorithm for Comparing Trees via Unbalanced Bipartite Matchings, journal=Journal of Algorithms, date=August 2001, volume=40, issue=2, pages=212–233, doi=10.1006/jagm.2001.1163, arxiv=cs/0101010 Computational problems in graph theory