Analyze the Optical Maps

This week, I presented the paper about Optical Maps with my group members. And I focus on how to reconstruct the whole genome map. Here I will discuss how can we reconstruct the whole genome map using the maps generated from Optical Maps.

 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.