Algebraic Statistics for Computational Biology

by Edited by L. Pachter , B. Sturmfels

• ISBN13: 9780521857000
• ISBN10: 0521857007
• Format: Hardcover
• Copyright: 2005-08-22
• Publisher: Cambridge University Press

Summary

The quantitative analysis of biological sequence data is based on methods from statistics coupled with efficient algorithms from computer science. Algebra provides a framework for unifying many of the seemingly disparate techniques used by computational biologists. This book offers an introduction to this mathematical framework and describes tools from computational algebra for designing new algorithms for exact, accurate results. These algorithms can be applied to biological problems such as aligning genomes, finding genes and constructing phylogenies. The first part of this book consists of four chapters on the themes of Statistics, Computation, Algebra and Biology, offering speedy, self-contained introductions to the emerging field of algebraic statistics and its applications to genomics. In the second part, the four themes are combined and developed to tackle real problems in computational genomics. As the first book in the exciting and dynamic area, it will be welcomed as a text for self-study or for advanced undergraduate and beginning graduate courses.

Table of Contents

Preface	ix
Guide to the chapters	xi
Acknowledgment of support	xii
Part I Introduction to the four themes	1	(160)
Statistics	3	(40)
L. Pachter
B. Sturmfels
Statistical models for discrete data	4	(5)
Linear models and toric models	9	(8)
Expectation Maximization	17	(7)
Markov models	24	(9)
Graphical models	33	(10)
Computation	43	(42)
L. Pachter
B. Sturmfels
Tropical arithmetic and dynamic programming	44	(5)
Sequence alignment	49	(10)
Polytopes	59	(8)
Trees and metrics	67	(8)
Software	75	(10)
Algebra	85	(40)
L. Pachter
B. Sturmfels
Varieties and Grobner bases	86	(8)
Implicitization	94	(8)
Maximum likelihood estimation	102	(7)
Tropical geometry	109	(8)
The tree of life and other tropical varieties	117	(8)
Biology	125	(36)
L. Pachter
B. Sturmfels
Genomes	126	(6)
The data	132	(5)
The problems	137	(4)
Statistical models for a biological sequence	141	(6)
Statistical models of mutation	147	(14)
Part II Studies on the four themes	161	(242)
Parametric Inference	165	(16)
R. Mihaescu
Tropical sum-product decompositions	166	(3)
The polytope propagation algorithm	169	(4)
Algorithm complexity	173	(4)
Specialization of parameters	177	(4)
Polytope Propagation on Graphs	181	(12)
M. Joswig
Polytopes from directed acyclic graphs	181	(4)
Specialization to hidden Markov models	185	(1)
An implementation in polymake	186	(5)
Returning to our example	191	(2)
Parametric Sequence Alignment	193	(13)
C. Dewey
K. Woods
Few alignments are optimal	193	(2)
Polytope propagation for alignments	195	(4)
Retrieving alignments from polytope vertices	199	(3)
Biologically correct alignments	202	(4)
Bounds for Optimal Sequence Alignment	206	(9)
S. Elizalde
F. Lam
Alignments and optimality	206	(2)
Geometric interpretation	208	(3)
Known bounds	211	(1)
The square root conjecture	212	(3)
Inference Functions	215	(11)
S. Elizalde
What is an inference function?	215	(2)
The few inference functions theorem	217	(3)
Inference functions for sequence alignment	220	(6)
Geometry of Markov Chains	226	(11)
E. Kuo
Viterbi sequences	226	(3)
Two- and three-state Markov chains	229	(2)
Markov chains with many states	231	(2)
Fully observed Markov models	233	(4)
Equations Defining Hidden Markov Models	237	(13)
N. Bray
J. Morton
The hidden Markov model	237	(1)
Grobner bases	238	(2)
Linear algebra	240	(7)
Combinatorially described invariants	247	(3)
The EM Algorithm for Hidden Markov Models	250	(14)
I. B. Hallgrimsdottir
R. A. Milowski
J. Yu
The EM algorithm for hidden Markov models	250	(4)
An implementation of the Baum--Welch algorithm	254	(3)
Plots of the likelihood surface	257	(4)
The EM algorithm and the gradient of the likelihood	261	(3)
Homology Mapping with Markov Random Fields	264	(14)
A. Caspi
Genome mapping	264	(3)
Markov random fields	267	(3)
MRFs in homology assignment	270	(3)
Tractable MAP inference in a subclass of MRFs	273	(3)
The Cystic Fibrosis Transmembrane Regulator	276	(2)
Mutagenetic Tree Models	278	(13)
N. Beerenwinkel
M. Drton
Accumulative evolutionary processes	278	(1)
Mutagenetic trees	279	(3)
Algebraic invariants	282	(5)
Mixture models	287	(4)
Catalog of Small Trees	291	(14)
M. Casanellas
L. D. Garcia
S. Sullivant
Notation and conventions	291	(4)
Fourier coordinates	295	(2)
Description of website features	297	(1)
Example	298	(5)
Using the invariants	303	(2)
The Strand Symmetric Model	305	(17)
M. Casanellas
S. Sullivant
Matrix-valued Fourier transform	306	(4)
Invariants for the 3-taxa tree	310	(4)
G-tensors	314	(4)
Extending invariants	318	(1)
Reduction to K1,3	319	(3)
Extending Tree Models to Splits Networks	322	(13)
D. Bryant
Trees, splits and splits networks	322	(3)
Distance-based models for trees and splits graphs	325	(1)
A graphical model on a splits network	326	(1)
Group-based mutation models	327	(3)
Group-based models for trees and splits	330	(2)
A Fourier calculus for splits networks	332	(3)
Small Trees and Generalized Neighbor-Joining	335	(12)
M. Contois
D. Levy
From alignments to dissimilarity	335	(2)
From dissimilarity to trees	337	(5)
The need for exact solutions	342	(2)
Jukes--Cantor triples	344	(3)
Tree Construction using Singular Value Decomposition	347	(12)
N. Eriksson
The general Markov model	347	(1)
Flattenings and rank conditions	348	(3)
Singular Value Decomposition	351	(1)
Tree-construction algorithm	352	(3)
Performance analysis	355	(4)
Applications of Interval Methods to Phylogenetics	359	(16)
R. Sainudiin
R. Yoshida
Brief introduction to interval analysis	360	(6)
Enclosing the likelihood of a compact set of trees	366	(1)
Global optimization	366	(5)
Applications to phylogenetics	371	(4)
Analysis of Point Mutations in Vertebrate Genomes	375	(12)
J. Al-Aidroos
S. Snir
Estimating mutation rates	375	(3)
The ENCODE data	378	(1)
Synonymous substitutions	379	(2)
The rodent problem	381	(6)
Ultra-Conserved Elements in Vertebrate and Fly Genomes	387	(16)
M. Drton
N. Eriksson
G. Leung
The data	387	(3)
Ultra-conserved elements	390	(2)
Biology of ultra-conserved elements	392	(8)
Statistical significance of ultra-conservation	400	(3)
References	403	(15)
Index	418