14 - Phylogenetic estimation: optimization problems, heuristics, and performance analysis

Summary

Phylogenetic trees, also known as evolutionary trees, are fundamental to many problems in biological and biomedical research, including protein structure and function estimation, drug design, estimating the origins of mankind, etc. However, the estimation of a phylogeny is enormously challenging from a computational standpoint, often involving months or more of computer time in order to produce estimates of evolutionary histories. Even these month-long analyses are not guaranteed to produce accurate estimates of evolution, for a variety of reasons. In addition to the errors in phylogeny estimation produced by limited amounts of data, there is the added – and critically important – fact that all the best phylogeny estimation methods are based upon heuristics for optimization problems that are difficult to solve. Consequently, large data sets are often “solved” only approximately. In this chapter, we discuss the issues involved in phylogeny estimation, as well as the technical term from computer science, “NP-hard.”

Introduction

One of the most exciting research topics in biology is the investigation of how life evolved on earth, ranging from questions concerned with very early evolution (e.g. What did the earliest organisms look like? Are fungi or plants closer to each other than either is to animals?) to more recent evolution (e.g. What is the relationship between humans, chimps, and gorillas? Where did human life begin? How did human populations migrate around the world?). However, interest in evolutionary histories is not restricted to species trees, as biologists are also interested in how protein families have evolved, and the evolution of function within protein families.