### Abstract

Inferring the consensus of a set of different evolutionary trees for a given species set is a well-studied problem, for which several different models have been proposed. In this paper, we propose a new optimization problem for consensus tree construction, which we call the asymmetric median tree, or AMT. Our main theoretical result is the equivalence between the asymmetric median tree problem on k trees and the maximum independent set (MIS) problem on k-colored graphs. Although the problem is NP-hard for three or more trees, we have polynomial time algorithms to construct the AMT for two trees and an approximation algorithm for three or more trees. We define a measure of phylogenetic resolution and show that our algorithms (both exact and approximate) produce consensus trees that on every input are at least as resolved as the standard models (strict consensus and majority tree) in use. Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use.

Original language | English (US) |
---|---|

Title of host publication | Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings |

Editors | Gene Myers, Dan Hirschberg |

Publisher | Springer-Verlag |

Pages | 234-252 |

Number of pages | 19 |

ISBN (Print) | 3540612580, 9783540612582 |

DOIs | |

State | Published - Jan 1 1996 |

Externally published | Yes |

Event | 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 - Laguna Beach, United States Duration: Jun 10 1996 → Jun 12 1996 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1075 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996 |
---|---|

Country | United States |

City | Laguna Beach |

Period | 6/10/96 → 6/12/96 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings*(pp. 234-252). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1075). Springer-Verlag. https://doi.org/10.1007/3-540-61258-0_18

**The asymmetric median tree - A new model for building consensus trees.** / Phillips, Cynthia; Warnow, Tandy.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1075, Springer-Verlag, pp. 234-252, 7th Annual Symposium on Combinatorial Pattern Matching, CPM 1996, Laguna Beach, United States, 6/10/96. https://doi.org/10.1007/3-540-61258-0_18

}

TY - GEN

T1 - The asymmetric median tree - A new model for building consensus trees

AU - Phillips, Cynthia

AU - Warnow, Tandy

PY - 1996/1/1

Y1 - 1996/1/1

N2 - Inferring the consensus of a set of different evolutionary trees for a given species set is a well-studied problem, for which several different models have been proposed. In this paper, we propose a new optimization problem for consensus tree construction, which we call the asymmetric median tree, or AMT. Our main theoretical result is the equivalence between the asymmetric median tree problem on k trees and the maximum independent set (MIS) problem on k-colored graphs. Although the problem is NP-hard for three or more trees, we have polynomial time algorithms to construct the AMT for two trees and an approximation algorithm for three or more trees. We define a measure of phylogenetic resolution and show that our algorithms (both exact and approximate) produce consensus trees that on every input are at least as resolved as the standard models (strict consensus and majority tree) in use. Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use.

AB - Inferring the consensus of a set of different evolutionary trees for a given species set is a well-studied problem, for which several different models have been proposed. In this paper, we propose a new optimization problem for consensus tree construction, which we call the asymmetric median tree, or AMT. Our main theoretical result is the equivalence between the asymmetric median tree problem on k trees and the maximum independent set (MIS) problem on k-colored graphs. Although the problem is NP-hard for three or more trees, we have polynomial time algorithms to construct the AMT for two trees and an approximation algorithm for three or more trees. We define a measure of phylogenetic resolution and show that our algorithms (both exact and approximate) produce consensus trees that on every input are at least as resolved as the standard models (strict consensus and majority tree) in use. Finally, we show that the AMT combines desirable features of many of the standard consensus tree models in use.

UR - http://www.scopus.com/inward/record.url?scp=84857044524&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84857044524&partnerID=8YFLogxK

U2 - 10.1007/3-540-61258-0_18

DO - 10.1007/3-540-61258-0_18

M3 - Conference contribution

AN - SCOPUS:84857044524

SN - 3540612580

SN - 9783540612582

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 234

EP - 252

BT - Combinatorial Pattern Matching - 7th Annual Symposium, CPM 1996, Proceedings

A2 - Myers, Gene

A2 - Hirschberg, Dan

PB - Springer-Verlag

ER -