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
• Priority queues
• Hash tables
• 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
• Bipartite graphs
• Graph coloring
• 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