Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2008 Jul 1;24(13):1481-8.
doi: 10.1093/bioinformatics/btn231. Epub 2008 May 12.

A distance metric for a class of tree-sibling phylogenetic networks

Gabriel Cardona  1 , Mercè Llabrés, Francesc Rosselló, Gabriel Valiente
Affiliations

A distance metric for a class of tree-sibling phylogenetic networks

Gabriel Cardona et al. Bioinformatics. .

Abstract

Motivation: The presence of reticulate evolutionary events in phylogenies turn phylogenetic trees into phylogenetic networks. These events imply in particular that there may exist multiple evolutionary paths from a non-extant species to an extant one, and this multiplicity makes the comparison of phylogenetic networks much more difficult than the comparison of phylogenetic trees. In fact, all attempts to define a sound distance measure on the class of all phylogenetic networks have failed so far. Thus, the only practical solutions have been either the use of rough estimates of similarity (based on comparison of the trees embedded in the networks), or narrowing the class of phylogenetic networks to a certain class where such a distance is known and can be efficiently computed. The first approach has the problem that one may identify two networks as equivalent, when they are not; the second one has the drawback that there may not exist algorithms to reconstruct such networks from biological sequences.

Results: We present in this article a distance measure on the class of semi-binary tree-sibling time consistent phylogenetic networks, which generalize tree-child time consistent phylogenetic networks, and thus also galled-trees. The practical interest of this distance measure is 2-fold: it can be computed in polynomial time by means of simple algorithms, and there also exist polynomial-time algorithms for reconstructing networks of this class from DNA sequence data.

Availability: The Perl package Bio::PhyloNetwork, included in the BioPerl bundle, implements many algorithms on phylogenetic networks, including the computation of the distance presented in this article.

Supplementary information: Some counterexamples, proofs of the results not included in this article, and some computational experiments are available at Bioinformatics online.

PubMed Disclaimer

Figures

Fig. 1.
Fig. 1.
Node v is quasi-sibling of u.
Fig. 2.
Fig. 2.
A sbTSTC phylogenetic network.
Fig. 3.
Fig. 3.
The transformation that produces Nn+1 from Nn.
Fig. 4.
Fig. 4.
sbTSTC phylogenetic networks with maximum number of nodes, with 3, 4 and 5 leaves.
Fig. 5.
Fig. 5.
The T reduction.
Fig. 6.
Fig. 6.
The TR reduction.
Fig. 7.
Fig. 7.
The Hr reduction.
Fig. 8.
Fig. 8.
The HR reduction.
Fig. 9.
Fig. 9.
Reduction processes for network in Figure 2.
Fig. 10.
Fig. 10.
Tree T (top) and networks N1 (middle), N2 (bottom) from (Jin et al., 2007b, Fig. 10).
See this image and copyright information in PMC

References

    1. Bandelt H-J, Dress A. Weak hierarchies associated with similarity measures—an additive clustering technique. Bull. Math. Biol. 1986;51:133–166. - PubMed
    1. Bandelt H-J. Phylogenetic networks. Verh. Naturwiss. Ver. Hambg. 1994;34:51–71.
    1. Baroni M, et al. Hybrids in real time. Syst. Biol. 2006;55:46–56. - PubMed
    1. Bereg S, Zhang Y. Phylogenetic networks based on the molecular clock hypothesis; Proceeding of the Fifth IEEE International Symposium on Bioinformatic and Bioengineering (BIBE 2005); IEEE Computer Society, Minneapolis, MN. 2005. pp. 320–323.
    1. Burkhardt F, Smith S. The Correspondence of Charles Darwin. Vol. 2. Cambridge: Cambridge University Press; 1987.

Publication types