A Mathematical Optimization Problem in Bioinformatics

Abstract

This article describes the sequence alignment problem in bioinformatics. Through examples, we formulate sequence alignment as an optimization problem and show how to compute the optimal alignment with dynamic programming. The examples and sample exercises have been used by the author in a specialized course in bioinformatics, but could be adapted to mathematics courses in which mathematical optimization or algorithms are discussed.

Keywords:

• Bioinformatics
• DNA
• optimization
• dynamic programming
• sequence alignment

ACKNOWLEDGEMENTS

I thank Gary Stormo for showing me the sequence alignment problem, and opening the door to a career in bioinformatics for me. John Williamson and Mike Waterman helped me keep a mathematician's perspective in this field, and I am grateful for their advice and guidance. I appreciate the opportunity to teach bioinformatics to undergraduates at Davidson College, and thank my mathematics department colleagues and my collaborator Malcolm Campbell for encouraging me to do so. Thanks to Rob Hochberg for teaching me the easy way to count global alignments, and to the referees and editors for suggesting several improvements to this manuscript. Special thanks to Glenn Ledder for his careful reading and organizing this special issue.