Format

Send to

Choose Destination
See comment in PubMed Commons below
IEEE/ACM Trans Comput Biol Bioinform. 2013 Jan-Feb;10(1):61-72. doi: 10.1109/TCBB.2012.133.

Mathematical properties of the deep coalescence cost.

Author information

  • 1Department of Computer Science, University of Tuebingen, 72076 Tuebingen, Germany. cuong.van-than@uni-tuebingen.de

Abstract

In the minimizing-deep-coalescences (MDC) approach for species tree inference, a tree that has the minimal deep coalescence cost for reconciling a collection of gene trees is taken as an estimate of the species tree topology. The MDC method possesses the desirable Pareto property, and in practice it is quite accurate and computationally efficient. Here, in order to better understand the MDC method, we investigate some properties of the deep coalescence cost. We prove that the unit neighborhood of either a rooted species tree or a rooted gene tree under the deep coalescence cost is exactly the same as the tree's unit neighborhood under the rooted nearest-neighbor interchange (NNI) distance. Next, for a fixed species tree, we obtain the maximum deep coalescence cost across all gene trees as well as the number of gene trees that achieve the maximum cost. We also study corresponding problems for a fixed gene tree.

[PubMed - indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments
How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for IEEE Engineering in Medicine and Biology Society
    Loading ...
    Write to the Help Desk