| Untangling tanglegrams: comparing trees by their drawings. | |
| | |
MedLine Citation:
|
PMID: 20530818 Owner: NLM Status: In-Process |
Abstract/OtherAbstract:
|
A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in biology--to compare evolutionary histories of host and parasite species and to analyze genes of species in the same geographical area. We consider optimization problems in tanglegram drawings. We show a linear time algorithm to decide if a tanglegram admits a planar embedding by a reduction to the planar graph drawing problem. This problem was also studied by Fernau et al. A similar reduction to a graph crossing problem also helps to solve an open problem they posed, showing a fixed-parameter tractable algorithm for minimizing the number of crossings over all d-ary trees. For the case where one tree is fixed, we show an O(n log n) algorithm to determine the drawing of the second tree that minimizes the number of crossings. This improves the bound from earlier methods. We introduce a new optimization criterion using Spearman's footrule distance and give an O(n²) algorithm. We also show integer programming formulations to quickly obtain tanglegram drawings that minimize the two optimization measures discussed. We prove lower bounds on the maximum gap between the optimal solution and the heuristic of Dwyer and Schreiber to minimize crossings. |
| | |
Authors:
|
Balaji Venkatachalam; Jim Apple; Katherine St John; Dan Gusfield |
Related Documents
:
|
11508458 - Resolution of two-way data: theoretical background and practical problem-solving. part ... 1113088 - Test of an information-processing model of humor: physiological response changes during... 3717178 - Solving problems through staff participation in focus groups. 20562048 - Design of recurrent neural networks for solving constrained least absolute deviation pr... 20859108 - Strategies for addressing adherence problems in patients with serious and persistent me... 4056168 - Staff perceptions of adolescent behaviour problems. |
Publication Detail:
|
Type: Journal Article; Research Support, U.S. Gov't, Non-P.H.S. |
Journal Detail:
|
Title: IEEE/ACM transactions on computational biology and bioinformatics / IEEE, ACM Volume: 7 ISSN: 1557-9964 ISO Abbreviation: IEEE/ACM Trans Comput Biol Bioinform Publication Date: 2010 Oct-Dec |
Date Detail:
|
Created Date: 2010-11-05 Completed Date: - Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 101196755 Medline TA: IEEE/ACM Trans Comput Biol Bioinform Country: United States |
Other Details:
|
Languages: eng Pagination: 588-97 Citation Subset: IM |
Affiliation:
|
Department of Computer Science, UC Davis, One Shields Avenue, Davis, CA 95616, USA. balaji@cs.ucdavis.edu |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Spatio-Angular Prefiltering for Multiview 3D Displays.
Next Document: Aging brains and waning clocks on the process of habituation.