Integrating bioinformatics and algorithm design

A staple in any accredited undergraduate curriculum in Computer Science is a course in ´The Design and Analysis of Algorithms´. Additionally, an increasing number of universities now offer bioinformatics courses and majors. This paper provides some specific algorithms and problems from bioinformatics that can be used to illustrate a variety of design techniques in an algorithms course. It first describes some fundamental biochemical prerequisite knowledge needed for a basic understanding of bioinformatics. The paper then discusses the major algorithm design techniques including brute force, divide-and-conquer, transform-and-conquer, dynamic programming, and the greedy approach. For each of these design techniques, the bioinformatics problem of nucleotide and protein sequence alignment is discussed and solved. The motivation for this project stems from a desire to spice up the traditional ´Design and Analysis of Algorithms´ course by introducing students to concepts from the exciting and rapidly expanding field of bioinformatics.