Multiple aligment - methods
Simultaneous: N-wise alignment (adapted from pairwise approach)
- uses N-dimension matrix.
- Complexity is
- O(m1m2) [2 sequences length m1 & m2 ]
- O(mn) [n sequences of length m]
- Thus only good for short sequences.
Progessive (heuristic) e.g. ClustalW:
- compute pairwise sequence identities
- construct binary tree (can output phylogenetic tree)
- align similar sequences in pairs, add distantly related ones later.