A few logs suffice to build (almost) all trees (I)

Type of content
Discussion / Working Papers
Publisher's DOI/URI
Thesis discipline
Degree name
Research Report
Publisher
University of Canterbury. Dept. of Mathematics
Journal Title
Journal ISSN
Volume Title
Language
Date
1997
Authors
Erdős, Péter L.
Steel, M.A.
Székely, L.A.
Abstract

A phylogenetic tree (also called an "evolutionary tree") is a leaf-labelled tree which represents the evolutionary history for a set of species, and the construction of such trees is a fundamental problem in biology. Here we address the issue of how many sequence sites are required in order to recover the tree with high probability when the sites evolve under standard Markov-style i.i.d. mutation models. We provide analytic upper and lower bounds for the required sequence length, by developing a new (and polynomial time) algorithm. In particular we show that when the mutation probabilities are bounded the required sequence length can grow surprisingly slowly (a power of log 𝑛) in the number 𝑛 of sequences, for almost all trees.

Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Field of Research::01 - Mathematical Sciences
Rights
Copyright Péter L. Erdős