Practical: Implementing shortest common superstring

Loading...

En provenance du cours de Johns Hopkins University

Algorithms for DNA Sequencing

391 notes

Johns Hopkins University

Algorithms for DNA Sequencing

391 notes

Cours 4 sur 8 dans Specialization Genomic Data Science

We will learn computational methods -- algorithms and data structures -- for analyzing DNA sequencing data. We will learn a little about DNA, genomics, and how DNA sequencing is used. We will use Python to implement key algorithms and data structures and to analyze real genomes and DNA sequencing datasets.

À partir de la leçon

Algorithms for assembly

In the last module we began our discussion of the assembly problem and we saw a couple basic principles behind it. In this module, we'll learn a few ways to solve the alignment problem.

Module 4 introduction 1:27

Lecture: The shortest common superstring problem8:11

Practical: Implementing shortest common superstring 4:30

Lecture: Greedy shortest common superstring7:57

Practical: Implementing greedy shortest common superstring 7:18

Lecture: Third law of assembly: repeats are bad5:58

Lecture: De Bruijn graphs and Eulerian walks8:31

Practical: Building a De Bruijn graph 4:47

Lecture: When Eulerian walks go wrong9:50

Lecture: Assemblers in practice8:27

Lecture: The future is long?9:36

Lecture: Computer science and life science5:25

Lecture: Thank yous 0:43

Rencontrer les enseignants

Ben Langmead, PhD
Assistant Professor
Computer Science
Jacob Pritt

Department of Computer Science

In this practical, we'll be implementing the shortest common super string using

just a brute force method to check all the possible combinations of reads.

So to do this, we're going to use the overlap

function from a previous practical, so I've already pasted that in here.

We're also going to use the permutations function which we

saw in a previous practical.

So I'm going to import itertools.

Now I'm going to define a function, scs,

that will give me the shortest common superstring of a set of strings, ss.

And so I'm going to start by just defining my shortest super string just as none.

I'm going to say for each set of strings, for

each permutation of set of strings,

in itertools.permutations(ss).

So, when I don't have a second argument in permutations,

it will give me all of the complete permutations of this list.

So this will return every possible ordering of the reads in this list.

And so what I'm going to do is loop through every one of these permutations

and try to put these reads together in order, in the order that I have,

and see what the length of that superstring is.

And we'll just keep doing that until I get the shortest one that I can find.

So I have this permutation of strings.

My superstring is going to start out by just being the first string in that list.

And now I'm just going to loop through every other string in that list and

append them onto this.

So I'm going to say for i in range up to the number of

strings minus 1, since we've already had the first string, we can skip that one.

I"m going to find the overlap length between the current string and

the next one.

Trying to get the ith string, the i plus one string.

I'm going to set the min_length to be 1.

And now, I'm going to take my superstring and append onto it,

the part of the next string that doesn't overlap that.

So that's going to be the suffix from the overlap length to the end, just like that.

And so now once I've finished this I've concatenated all these strings,

overlapping them as much as I can to get the superstring.

So now I'm going to test if this super string is smaller than the shortest one

I've seen so far.

So I'm going to say if my shortest super string

is none, or the length of my current super string is less than

the length of the shortest super string,

then I'm just going to replace the shortest superstring with my superstring.

And then when I'm done I just return the shortest superstring that I see.

>> So that loop is going to loop a large number of times.

If we add the n strings it's going to loop n factorial times.

But one of those iterations is going to give us the shortest

possible super string, so we'll return that and that's the right answer.

>> Mm-hm.

So now I can just remember this function on the set of strings.

And so I have my strings here.

This is the shortest common super string.

You can see the third string here

overlaps by four characters with this string here, so it goes first.

And then this first string overlaps the second string by about four characters.

So it's combined them like that, and

given us the shortest superstring that we can get from these reads.

>> Mm-hm.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2019 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play