### Abstract

The construction of evolutionary trees is a fundamental problem in biology, and yet methods for reconstructing evolutionary trees are not reliable when it comes to inferring accurate topologies of large divergent evolutionary trees from realistic length sequences. We address this problem and present a new polynomial time algorithm for reconstructing evolutionary trees called the Short Quartets Method which is consistent and which has greater statistical power than other polynomial time methods, such as Neighbor-Joining and the 3-approximation algorithm by Agarwala et al. (and the “Double Pivot” variant of the Agarwala et al. algorithm by Cohen and Farach) for the Loo-nearest tree problem. Our study indicates that our method will produce the correct topology from shorter sequences than can be guaranteed using these other methods.

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

Title of host publication | Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings |

Editors | Pierpaolo Degano, Roberto Gorrieri, Alberto Marchetti-Spaccamela |

Publisher | Springer-Verlag |

Pages | 827-837 |

Number of pages | 11 |

ISBN (Print) | 3540631658, 9783540631651 |

State | Published - Jan 1 1997 |

Externally published | Yes |

Event | 24th International Colloquium on Automata, Languages and Programming, ICALP 1997 - Bologna, Italy Duration: Jul 7 1997 → Jul 11 1997 |

### Publication series

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

Volume | 1256 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 24th International Colloquium on Automata, Languages and Programming, ICALP 1997 |
---|---|

Country | Italy |

City | Bologna |

Period | 7/7/97 → 7/11/97 |

### Fingerprint

### ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

### Cite this

*Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings*(pp. 827-837). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1256). Springer-Verlag.

**Constructing big trees from short sequences.** / Erdős, Péter L.; Steel, Michael A.; Székely, László A.; Warnow, Tandy J.

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

*Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings.*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1256, Springer-Verlag, pp. 827-837, 24th International Colloquium on Automata, Languages and Programming, ICALP 1997, Bologna, Italy, 7/7/97.

}

TY - GEN

T1 - Constructing big trees from short sequences

AU - Erdős, Péter L.

AU - Steel, Michael A.

AU - Székely, László A.

AU - Warnow, Tandy J.

PY - 1997/1/1

Y1 - 1997/1/1

N2 - The construction of evolutionary trees is a fundamental problem in biology, and yet methods for reconstructing evolutionary trees are not reliable when it comes to inferring accurate topologies of large divergent evolutionary trees from realistic length sequences. We address this problem and present a new polynomial time algorithm for reconstructing evolutionary trees called the Short Quartets Method which is consistent and which has greater statistical power than other polynomial time methods, such as Neighbor-Joining and the 3-approximation algorithm by Agarwala et al. (and the “Double Pivot” variant of the Agarwala et al. algorithm by Cohen and Farach) for the Loo-nearest tree problem. Our study indicates that our method will produce the correct topology from shorter sequences than can be guaranteed using these other methods.

AB - The construction of evolutionary trees is a fundamental problem in biology, and yet methods for reconstructing evolutionary trees are not reliable when it comes to inferring accurate topologies of large divergent evolutionary trees from realistic length sequences. We address this problem and present a new polynomial time algorithm for reconstructing evolutionary trees called the Short Quartets Method which is consistent and which has greater statistical power than other polynomial time methods, such as Neighbor-Joining and the 3-approximation algorithm by Agarwala et al. (and the “Double Pivot” variant of the Agarwala et al. algorithm by Cohen and Farach) for the Loo-nearest tree problem. Our study indicates that our method will produce the correct topology from shorter sequences than can be guaranteed using these other methods.

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

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

M3 - Conference contribution

AN - SCOPUS:84951102016

SN - 3540631658

SN - 9783540631651

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

SP - 827

EP - 837

BT - Automata, Languages and Programming - 24th International Colloquium, ICALP 1997, Proceedings

A2 - Degano, Pierpaolo

A2 - Gorrieri, Roberto

A2 - Marchetti-Spaccamela, Alberto

PB - Springer-Verlag

ER -