1. The Minimum Evolution Problem in Phylogenetics: Polytopes, Linear Programming, and Interpretation
- Author
-
Logan Keefe, Gabriela Hamerlinck, William Sands, and Stefan Forcey
- Subjects
Branching (linguistics) ,Theoretical computer science ,Phylogenetic tree ,Distance matrix ,Linear programming ,Phylogenetics ,Computer science ,Polytope ,Greedy algorithm ,Neighbor joining - Abstract
Biologists use phylogenetic trees, or phylogenies, to visualize genetic relatedness of organisms. Phylogenetic trees can be used at any scales—from determining the population structure of a single species, to displaying all life on planet Earth—under the assumption of a branching tree-like structure. This chapter introduces the key concept of using a distance matrix (created from genetic data) in order to infer phylogenies via the principle of Balanced Minimum Evolution (BME). Then we focus on finding the phylogeny via linear programming techniques, especially branch-and-bound on relaxations of the BME polytope. Related methods for finding a BME phylogeny include edge-walking with tree moves (as in the program FastMe ) and Neighbor Joining, a popular greedy algorithm for approximating the BME phylogeny. The skills used to infer and interpret a phylogenetic tree can be useful to many biological fields, including genetics and molecular biology, as well as applied research ranging from conservation of endangered species to tracking the spread of infectious diseases.
- Published
- 2019
- Full Text
- View/download PDF