Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/85204
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Type: | Conference paper |
Title: | Computing a consensus of multilabeled trees |
Author: | Huber, K. Moulton, V. Spillner, A. Suchecki, R. |
Citation: | Proceedings of the Workshop on Algorithm Engineering and Experiments, 2012 / Bader, D.A., Mutzel, P. (ed./s), pp.84-92 |
Publisher: | Society for Industrial and Applied Mathematics |
Issue Date: | 2012 |
ISBN: | 9781618396242 |
ISSN: | 2164-0300 |
Conference Name: | 14th Meeting on Algorithm Engineering and Experiments 2012 (ALENEX12) (16 Jan 2012 - 16 Jan 2012 : Kyoto, Japan) |
Editor: | Bader, D.A. Mutzel, P. |
Statement of Responsibility: | Katharina T. Huber, Vincent Moulton, Andreas Spillner, Sabine Storandt and Radoslaw Suchecki |
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 runtime 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. Copyright © SIAM. |
Rights: | Copyright status unknown |
DOI: | 10.1137/1.9781611972924.9 |
Published version: | http://dx.doi.org/10.1137/1.9781611972924.9 |
Appears in Collections: | Aurora harvest 2 Australian Centre for Plant Functional Genomics publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.