Motivation
Goal: Compare a new sequence to a reference sequence, to see whether there is any difference.
The most straightforward way is aligning two nucleotide sequence, however:
(1) Experimental expensive.
(2) Computational expensive: the complexity of aligning two sequences is O(mn), m, n are the length of the sequences.
Analyze result of optical map
What we get after optical map?
Input: a lot of segments of genome.
Output: For each segment, we know the cut position, and the size between every two cut.
Goal
Goal: Reconstruct the whole genome restriction map, align it to the reference sequence, check the variation.
Cluster
Goal: Find the cluster of segments which belong to the same region in the reference sequence.
Algorithm: Local optimal alignment.
Assemble
Goal: For each cluster, find a consensus map.
Algorithm: Multiple alignment.
Pairwise alignment
Goal: Align each assembled map contig to the reference sequence.
Algorithm: local optimal alignment.
