Computational Biology - Lecture 3

Today, we review some basics of combinatorial geometry:

• Convex sets and polytopes.
• Affine hulls and affine spaces.
• Positive hulls and cones.
• Hyperplanes and half-spaces.
• Faces, f-vectors.
• Normal cones and normal fans.

The aim of the next lecture will be to interpret the product-sum decomposition of the marginal probabilities in the pair hidden Markov model in terms of the polytope algebra. This will provide a way to determine all optimal pairwise sequence alignments.