Abstract
In this paper we consider two challenging problems
that arise in the context of computing a consensus of
a collection of multilabeled trees, namely (1) selecting a
compatible collection of clusters on a multiset from an
ordered list of such clusters and (2) optimally refining
high degree vertices in a multilabeled tree. Forming
such a consensus is part of an approach to reconstruct
the evolutionary history of a set of species for which
events such as genome duplication and hybridization
have occurred in the past. We present exact algorithms
for solving (1) and (2) that have an exponential run-
time in the worst case. To give some impression of their
performance in practice, we apply them to simulated
input and to a real biological data set highlighting the
impact of several structural properties of the input on
the performance
| Original language | English |
|---|---|
| Pages | 84-92 |
| Number of pages | 9 |
| Publication status | Published - 16 Jan 2012 |
| Event | Meeting on Algorithm Engineering & Experiments (ALENEX12) - Kyoto, Japan Duration: 16 Jan 2012 → 16 Jan 2012 |
Conference
| Conference | Meeting on Algorithm Engineering & Experiments (ALENEX12) |
|---|---|
| Country/Territory | Japan |
| City | Kyoto |
| Period | 16/01/12 → 16/01/12 |