Part II - Studies on the four themes

Summary

The contributions in this part of the book were all written by students, postdocs and visitors who in some way were involved in the graduate course Algebraic Statistics for Computational Biology that we taught in the mathematics department at UC Berkeley during the fall of 2004. The eighteen chapters offer a more in-depth study of some of the themes which were introduced in Part I. Most of the chapters contain original research that has not been published elsewhere. Highlights among new research results include:

• New results about polytope propagation and parametric inference (Chapters 5, 6 and 8).

• An example of a biologically correct alignment which is not the optimal alignment for any choice of parameters in the pair HMM (Chapter 7).

• Theorem 9.3 which states that the number of inference functions of a graphical model grows polynomially for fixed number of parameters.

• Theorem 10.5 which states that, for alphabets with four or more letters, every toric Viterbi sequence is a Viterbi sequence.

• Explicit calculations of phylogenetic invariants for the strand symmetric model which interpolate between the general reversible model and group based models (Chapter 16).

• Tree reconstruction based on singular value decomposition (Chapter 19).

The other chapters also include new mathematical results or methodological advances in computational biology. Chapter 15 introduces a standardized framework for working with small trees. Even results on the smallest non-trivial tree (with three leaves) are interesting, and are discussed in Chapter 18. Similarly, Chapter 14 presents a unified algebraic statistical view of mutagenetic tree models.