## Computational Molecular Biology and Genomics:

Algorithms and Data Structures Concepts

Students are expected to be familiar with the following
concepts. While some of this material
will be reviewed in class, students are ultimately responsible for acquiring
any background knowledge they may be lacking.

### Resources

*Introduction
to Computational Molecular Biology, *J.C. Setubal and J. Meidanis,
chapter 2 (on reserve).
*
Computational Methods in Molecular Biology, *S. L. Salzberg,
D. B. Searls and S. Kasif,

Chapter 2: "A tutorial introduction to
computation for biologists". (electronic reserves)
*Computational
Biology* , P. Clote and R. Backofen, Sections 2.1.1 - 2.1.3
*Data Structures and Problem Solving using Java*, M. A. Weiss
*Introduction
to Algorithms*, T. H. H. Cormen
R. L. Rivest C. E.
Leiserson
- Dictionary of Algorithms and Data
Structures

### Strings

- Substrings,
superstrings, concatenation, prefix, suffix

### Algorithms and Data structures

- Pseudocode
- Divide and Conquer
- Dynamic
programming
- Stacks,
queues
- Linked lists
- Breadth
first search
- Depth
first search
- Binary
search trees
- Searching
- Sorting

### Graph theory

- Directed
vs undirected graphs
- Notation:
G = (V,E)
- V =
{nodes, aka vertices}
- E =
{edges}

- Cyclic
vs acyclic graphs, trees
- Representations:
matrix, adjacency lists
- Node
degree
- Paths
and cycles,
- Connected
components
- Minimum
spanning tree

### Algorithmic complexity

- Big
Oh notation
- Asymptotic
behavior
- "Hard" problems - NP-completeness

### Probability theory

- Random variables
- Conditional probability
- Bayes Theorem
- Hypothesis testing, p-values
- Markov chains
- Binomial distribution
- Geometric distribution
- Exponential distribution
- Normal distribution
- Poisson distribution