Greedy Algorithms Computer Science Engineering (CSE) Notes | EduRev

Computer Science Engineering (CSE) : Greedy Algorithms Computer Science Engineering (CSE) Notes | EduRev

 Page 1


1 
Outline 
 
• Today’s topic: greedy algorithms 
– Genome rearrangements 
• Sorting by reversals 
• Breakpoints 
– Shotgun sequencing 
• Fragment assembly: the shortest superstring problem 
• Finishing problem 
• Next time: greedy algorithms for motif finding 
 
Page 2


1 
Outline 
 
• Today’s topic: greedy algorithms 
– Genome rearrangements 
• Sorting by reversals 
• Breakpoints 
– Shotgun sequencing 
• Fragment assembly: the shortest superstring problem 
• Finishing problem 
• Next time: greedy algorithms for motif finding 
 
2 
Turnip vs Cabbage: Almost Identical mtDNA gene 
sequences 
• In 1980s Jeffrey Palmer studied evolutionary change 
in plant organelles by comparing mitochondrial 
genomes of the cabbage and turnip 
 
• 99% similarity between genes 
 
• These surprisingly identical gene sequences differed 
in gene order 
 
• This helped pave the way to analyzing genome 
rearrangements in molecular evolution 
Page 3


1 
Outline 
 
• Today’s topic: greedy algorithms 
– Genome rearrangements 
• Sorting by reversals 
• Breakpoints 
– Shotgun sequencing 
• Fragment assembly: the shortest superstring problem 
• Finishing problem 
• Next time: greedy algorithms for motif finding 
 
2 
Turnip vs Cabbage: Almost Identical mtDNA gene 
sequences 
• In 1980s Jeffrey Palmer studied evolutionary change 
in plant organelles by comparing mitochondrial 
genomes of the cabbage and turnip 
 
• 99% similarity between genes 
 
• These surprisingly identical gene sequences differed 
in gene order 
 
• This helped pave the way to analyzing genome 
rearrangements in molecular evolution 
3 
Turnip vs Cabbage: Different mtDNA Gene Order 
• Gene order comparison: 
 
Page 4


1 
Outline 
 
• Today’s topic: greedy algorithms 
– Genome rearrangements 
• Sorting by reversals 
• Breakpoints 
– Shotgun sequencing 
• Fragment assembly: the shortest superstring problem 
• Finishing problem 
• Next time: greedy algorithms for motif finding 
 
2 
Turnip vs Cabbage: Almost Identical mtDNA gene 
sequences 
• In 1980s Jeffrey Palmer studied evolutionary change 
in plant organelles by comparing mitochondrial 
genomes of the cabbage and turnip 
 
• 99% similarity between genes 
 
• These surprisingly identical gene sequences differed 
in gene order 
 
• This helped pave the way to analyzing genome 
rearrangements in molecular evolution 
3 
Turnip vs Cabbage: Different mtDNA Gene Order 
• Gene order comparison: 
 
4 
Turnip vs Cabbage: Different mtDNA Gene Order 
• Gene order comparison: 
 
Page 5


1 
Outline 
 
• Today’s topic: greedy algorithms 
– Genome rearrangements 
• Sorting by reversals 
• Breakpoints 
– Shotgun sequencing 
• Fragment assembly: the shortest superstring problem 
• Finishing problem 
• Next time: greedy algorithms for motif finding 
 
2 
Turnip vs Cabbage: Almost Identical mtDNA gene 
sequences 
• In 1980s Jeffrey Palmer studied evolutionary change 
in plant organelles by comparing mitochondrial 
genomes of the cabbage and turnip 
 
• 99% similarity between genes 
 
• These surprisingly identical gene sequences differed 
in gene order 
 
• This helped pave the way to analyzing genome 
rearrangements in molecular evolution 
3 
Turnip vs Cabbage: Different mtDNA Gene Order 
• Gene order comparison: 
 
4 
Turnip vs Cabbage: Different mtDNA Gene Order 
• Gene order comparison: 
 
5 
Turnip vs Cabbage: Different mtDNA Gene Order 
• Gene order comparison: 
 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Semester Notes

,

Previous Year Questions with Solutions

,

Extra Questions

,

MCQs

,

mock tests for examination

,

Summary

,

study material

,

Sample Paper

,

Viva Questions

,

pdf

,

shortcuts and tricks

,

Greedy Algorithms Computer Science Engineering (CSE) Notes | EduRev

,

ppt

,

Exam

,

Objective type Questions

,

practice quizzes

,

past year papers

,

Greedy Algorithms Computer Science Engineering (CSE) Notes | EduRev

,

video lectures

,

Important questions

,

Free

,

Greedy Algorithms Computer Science Engineering (CSE) Notes | EduRev

;