PHYLOGENETICS: HEURISTICS AND NEW PARADIGMS

Phylogenetic inference is an important question posed in biological research: what are the ancestor-descendent relationships between modern organisms?  Modern techniques of phylogenetic inference employ an optimality criterion in hypothesis selection (Maximum Parsimony, Maximum Likelihood, and Bayesian analysis).  Maximum parsimony attempts to minimize the number of transformations required to explain the observed characteristics among living organisms.  Its computational counterpart is known as the Steiner tree problem.  We present an overview of the hardness, most important algorithms, and heuristics employed for the Steiner tree problem under biologically interesting spaces such as  hamming, manhattan, discrete, edition, breakpoint, inversion, and double cut and join.