2-AIN-505, 2-AIN-251: Seminár z bioinformatiky (1) a (3)
Zima 2014
Abstrakt

Manuel Lafond, Krister M. Swenson, Nadia El-Mabrouk. An Optimal Reconciliation Algorithm for Gene Trees with Polytomies. In RECOMB 2012, pp. 106-122, 2012.

Download preprint: not available

Download from publisher: http://link.springer.com/chapter/10.1007/978-3-642-33122-0_9

Related web page: not available

Bibliography entry: BibTeX

Abstract:

Reconciliation is a method widely used to infer the evolutionary
relationship between the members of a gene family. It consists of
comparing a gene tree with a species tree, and interpreting the
incongruence between the two trees as evidence of duplication and
loss. In the case of binary rooted trees, linear-time algorithms
have been developed for the duplication, loss, and
mutation (duplication + loss) costs. However, a strict
prerequisite to reconciliation is to have a gene tree free from
error, as few misplaced edges may lead to a completely different
result in terms of the number and position of inferred
duplications and losses. How should the weak edges be handled?
One reasonable answer is to transform the binary gene tree into a
non-binary tree by removing each weak edge and collapsing its two
incident vertices into one. The created polytomies are “apparent”
as they do not reflect a true simultaneous divergence of many
copies from a common ancestor, but rather a lack of
resolution. In this paper, we consider the problem of reconciling
a non-binary rooted gene tree G with a binary rooted species tree
S, were polytomies of G are assumed to be apparent. We give a
linear-time algorithm that infers a reconciliation of minimum
mutation cost between a binary refinement of a polytomy and S,
improving on the best known result, which is cubic. This implies
a straightforward generalization to a gene tree G with nodes of
arbitrary degree, that runs in time O(|S||G|), which is shown to
be an optimal algorithm.