Notes of Bioinformatics IV

My NOTES of  Bioinformatics IV: Molecular Evolution

Chapter 7: Which Animal Gave Us SARS? (Evolutionary Tree Reconstruction)

In this chapter, we learned the algorithms of constructing evolutionary trees.

Distance-based Phylogeny Construction

1. distance matrix

- symmetric; non-negative; triangle inequality.

- non-additive v.s. additive.

2. Tree

- limb: an edge connecting a leaf to its parent.

- Distances Between Leaves Problem

- maximal non-branching tree

- Limb Length Problem

3. Algorithms

3.1 Additive Phylogeny Problem

3.2 Least Squares for Approximate Phylogenies

3.3 UPGMA: unweighted pair group method with arithmetic mean

- clustering heuristic

- yet the smallest element in the distance matrix does not necessarily correspond to a pair of neighboring leaves.

3.4 Neighbor-Joining 

- neighbor-joining matrix instead of distance matrix

Character-based Phylogeny Construction

1. character table

2. Small Parsimony Problem

- parsimony score

- dynamic programming algorithm

- SmallParsimony does not help us if we do not know the evolutionary tree in advance.

3. Large Parsimony Problem

- nearest neighbor interchange

Chapter 8: Was T.rex Just a Big Chicken? (Computational Proteomics)

1. peptide vector

2. spectral vector

3. spectrum graph: a node for each element of Spectrum, and directed edge labeled by the amino acid.

4. Score peptide against spectrum: dot product.

5. Peptide Identification Problem

6. spectral dictionary

7. PSM disctionary

8. Spectral Alignment Problem: todo