UMD CMSC 858W - Optical maps (2 pages)

Previewing page 1 of 2 page document View the full content.
View Full Document

Optical maps



Previewing page 1 of actual document.

View the full content.
View Full Document
View Full Document

Optical maps

48 views


Pages:
2
School:
University of Maryland, College Park
Course:
Cmsc 858w - Advanced Topics In Theory Of Computing: Algorithms For Biosequence Analysis
Unformatted text preview:

Optical maps Introduction Optical mapping is a technology that allows us to experimentally determine the relative position of certain landmarks usually restriction sites places where a specific restriction enzyme can cut the DNA usually recognized by a specific 6 8 bp sequence along a stretch of DNA Unlike sequencing optical maps provide long range information the fragments being mapped are usually on the order of several 100s of kbp however the information provided is sparse Thus optical mapping is useful as a complement to sequencing Also it can be used as a cheaper way than sequencing of getting information about the global structure of a genome Computationally an optical map is just an ordered list of sizes together with estimates of the error in the size estimates representing the list of gaps between adjacent restriction sites Mapping algorithm I ll focus here on just the problem of aligning an experimentally determined optical map to an in silico optical map constructed e g from the output of an assembler Formally the experimental map is represented as the array emap ok s k k 1 n where ok and sk are the size and standard deviation for fragment k The in silico map is ismap e k k 1 m where ek is the size of the corresponding fragment Aligning the two maps can be performed pretty easily using a dynamic programming algorithm similar to the sequence alignment algorithm Specifically V i j is the score of aligning the first i fragments from the experimental map to the first j fragments from the in silico map The recurrence equation is V i j mink i l j V k l score k i l j where score k i l j is a score of how well the set of fragments between k i and l j match each other This score can be defined as a combination of a 2 score and a penalty for missed sites i score k i l j j 2 s k o s t l e t i s k s 2s C i k l j where C is a constant that can be used to tune the contribution of the two components Interesting research directions Can optical maps be used to guide genome assembly How do you efficiently align maps to an already sequenced genome to identify structural variants How do you efficiently align two maps to each other to identify structural differences


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Optical maps and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Optical maps and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?