Explore
For Enterprise
Join for Free
Log In

Arts et humanités
Business
Informatique
Science des données
Technologies de l'information
santé
Mathématiques et logique
Développement personnel
Sciences physiques et ingénierie
Sciences sociales
Apprentissage des langues
Diplômes et Certificats

Explorez l'intégralité de Coursera

Parcourir
Rechercher
For Enterprise
Connexion
Inscrivez-vous gratuitement

Practical: Implementing shortest common superstring

Loading...

Algorithms for DNA Sequencing

Université Johns-Hopkins

4.8 (407 notes) | 16K étudiants inscrits

Cours 4 de 8 dans Science des données génomiques Spécialisation

Visualiser le programme de cours

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.

Compétences que vous apprendrez

Bioinformatics Algorithms, Algorithms, Python Programming, Algorithms On Strings

Avis

4.8 (407 notes)

5 stars
332 ratings
4 stars
60 ratings
3 stars
14 ratings
2 stars
1 ratings

MD

Nov 10, 2016

This was really fun. Really enjoyed the a-ha of the algorithms and the fun of solving the alignment and assembly problems. Feel mildly powerful after assembling a virus genome.

LK

Mar 12, 2016

Excellent intro to the computational challenges in analyzing genomic sequences.\n\nLectures and programming exercises explain algorithms very clearly even for beginners.

À 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

Enseigné par

Ben Langmead, PhD
Assistant Professor
Jacob Pritt

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

Coursera
À propos
Direction
Carrières
Catalogue
Certificats
Certificats MasterTrack™
Diplômes
For Enterprise
For Government

Communauté
Learners
Partners
Developers
Beta Testers
Translators

Se connecter
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Blog Tech

Plus
Conditions
Confidentialité
Aide
Accessibilité
Presse
Contact
Répertoire
Filiales