Illinois Genetic Algorithms Laboratory

The following CS colloquium sounds interesting:

Sensitivity Analysis for Markov Models of Evolution

   David Fernández-Baca
   Department of Computer Science
   Iowa State University
   Ames, Iowa

   March 14 (Monday), 2005 at 4:00 p.m.
   1404 Siebel Center for Computer Science

Understanding the evolution of biological sequences is one of the
fundamental problems in biology.  The goal is to construct an
evolutionary tree or phylogeny whose leaves are the given sequences and
whose internal nodes represent ancestral species.   A variety of
mathematical models have been proposed for this purpose. We consider a
simple but widely-used Markov model where sequences evolve through
random mutation. The objective is to find the evolutionary tree that
offers the most probable explanation for the input data.  A related
problem is ancestral reconstruction, where the tree is given and the
most likely ancestors must be inferred.

Implicit in Markov models is the notion of evolutionary distance:
Intuitively, the larger the distance between two sequences, the larger
the mutation probabilities.  These parameters, which are non-linear
functions of distance, have a strong influence on the solution to
phylogeny construction problems.  We present an algorithm that computes
the optimum solution to the ancestral reconstruction problem for all
possible values of the evolutionary distance.  The algorithm incurs only
a slight overhead relative to the effort needed to compute the answer
for any fixed value. Sensitivity analysis of this sort allows the
exploration of a range of evolutionary hypotheses; enabling one to
identify possibilities that are overlooked when only fixed distances are
considered.  The procedure also helps in assessing the robustness of the
inferences made from the model.  Our algorithm relies on the geometric
properties of the parameter space decomposition induced by a linear
version of the problem and uses divide-and-conquer.  We show that
similar techniques yield a fast procedure for a pair-wise sequence
comparison problem where the goal is to identify contiguous regions of
high similarity.

This is joint work with Balaji Venkatachalam and was partially supported
by National Science Foundation grants CCR-9988348 and EF-0334832.

Bio:
David Fernández-Baca is professor of Computer Science at Iowa State
University.  His research interests lie in sensitivity analysis in
combinatorial optimization, the construction of evolutionary trees, and
the problems arising at the boundaries of these two areas.  He is part
of the Phylota project (www.phylota.org), whose aim is to develop new
methods and software tools to help construct the genealogical “tree of
life” of all biological species. Phylota is funded by the National
Science Foundation’s ATOL (Assembling the Tree of Life) Program.

Dr. Fernández-Baca received a Bachelor’s degree in Computer Engineering
from the National University of Mexico in 1980, and a Master’s degree in
Computer Engineering and a PhD in Computer Science in 1983 and 1986,
respectively.