Are you interested in learning how to program (in Python) within a scientific setting? This course will cover algorithms for solving various biological problems along with a handful of programming challenges helping you implement these algorithms in Python. It offers a gently-paced introduction to our Bioinformatics Specialization (https://www.coursera.org/specializations/bioinformatics), preparing learners to take the first course in the Specialization, "Finding Hidden Messages in DNA" (https://www.coursera.org/learn/dna-analysis). Each of the four weeks in the course will consist of two required components. First, an interactive textbook provides Python programming challenges that arise from real biological problems. If you haven't programmed in Python before, not to worry! We provide "Just-in-Time" exercises from the Codecademy Python track (https://www.codecademy.com/learn/python). And each page in our interactive textbook has its own discussion forum, where you can interact with other learners. Second, each week will culminate in a summary quiz. Lecture videos are also provided that accompany the material, but these videos are optional.
Optional: Where in the Genome Does DNA Replication Begin? (Part 1)
Loading...
En provenance du cours de University of California San Diego
Biology Meets Programming: Bioinformatics for Beginners
462 notes
À partir de la leçon
Week 1
Where in the Genome Does Replication Begin? (Part 1)
Rencontrer les enseignants
Pavel PevznerProfessor
Department of Computer Science and Engineering
Phillip CompeauVisiting Researcher
Department of Computer Science & Engineering
Hello and welcome to the first lecture of the Bioinformatics Algorithms class!
When I started teaching bioinformatics two decades ago, one of the biggest challenges
was to connect with a very diverse audience. I had to talk to computer scientists and biologists,
to physicists and biochemists, to mathematicians and statisticians.
The challenge was how to keep computer scientists focused while explaining sometimes convoluted
biological concepts. And likewise, how to keep biologists awake
while explaining sometimes complex algorithmic ideas.
I hope that in this class we have an equally diverse audience, and that's why I decided
to start from a very simple problem. Here is the first problem in this class.
Given a string called Text1, copy it to a string called Text2.
And I see that some of you are already thinking about quitting this this class because it
is so trivial. Please wait. You might think that it is trivial,
but billions of cells (replicating your own genome right now) don't think so.
In fact, they are trying to accomplish the incredibly complex task of replicating genome.
Just think about this: you need to unwind DNA (two strands of DNA) and separate them.
You need to make sure that there are enough free-floating nucleotides so replication can
complete because if you start replication and you have to stop in the middle because
there is no energy left, you are dead. So, in this course, we will learn about this
and many other challenges related to replication. In fact, replication of the human genome is
so complex that biologists still do not fully understand how its done.
That's why we will focus on replication of bacterial genomes that are 1000 times smaller
(their genomes are 1000 times smaller) and that's why replicating bacterial genomes is
a little bit easier. I am not saying that it is trivial.
And in fact, right now, there are billions of bacterial cells trying to replicate bacterial
genomes inside you because the number of bacterial cells inside you is 10 times larger than the
number of your own human cells. Now, since bacteria usually have circular
chromosomes, I have to slightly change my problem.
My new problem is: Given a CIRCULAR genome called Text1, copy
it to a CIRCULAR Text2. It is equally trivial, but it makes some slight
changes in the setup that we need to address.
A circular genome does not have a start and an end, and that's why the roughly 5 million
nucleotide-long E. coli genome has a choice on where to start replication.
In this class, we will try to figure out where it starts because all E. coli cells on Earth
start replication in the same region, called the "origin of replication".
So, our first problem is "Where in the genome does it all begin?" and the only information
that we have is the genome itself. Let's go ahead and first try to answer the
question: What are the hidden messages in the replication origin that help the E. coli
genome figure out where to start.
And here is the first, or should I say the 3rd problem in this course: finding the origin
of replication. I'll give you a genome, you will have to give me the location of origin
of replication in this genome. Does the problem make sense?
Yes [from the audience] You may be right or wrong depending on who
you are. "Are you a computer scientist or a biologist?"
Computer scientist [from the audience] Then you are wrong. If you were a biologist
then you could think about an experiment. For example, you can start cutting short pieces
from DNA, and when you cut a piece and the cell suddenly lost ability to replicate, it
means that probably you cut out the origin of replication.
But if you are a computer scientist, you should just refuse solving this problem; it is an
ill-defined computational problem. So, how can we turn this ill-defined computational
problem into something that makes sense? Lets try to ask a question: "how does the
cell know to begin replication in short oriC region?"
There must be some hidden messages in the genome that tell the cell "Start replication
right here!" What are these hidden messages?
Let's first try to formulate the problem right. The right formulation will be the Hidden Message
Problem. In this case, Input is a string Text representing
the replication origin, and Output is the hidden message in Text.
Is this problem clear? If you feel this problem clear, please raise
your hands. 1, 2, 3, 4, 5, 6, 7, 8...
This problem is absolutely unclear.
It is equally poorly defined as the first problem I showed you. Indeed, Son is not happy
again because what is a hidden message? Have I described it? No.
So, for a computer scientist there is not even a starting point to address this problem.
But let's go two centuries back and let's see how somebody in a somewhat similar situation
tried to solve a similar problem. We go to "The Gold Bug" short story by Edgar
Allan Poe; in this story, the hero, whose name was Legrand, tried to decode the message
left by pirates. And his hope was that when he decoded the
message, he would be able to find pirate treasure, so he was quite motivated.
The only thing he saw is this text. How would you tell what is written, what is
coded in this text? What Legrand noticed is that a combination
of three symbols ";48" appears surprisingly frequently in this text.
Does it suggest an idea on what is written in the message?
Here is the hint: The message is in English" And here is another hint: "THE" is the most
frequent word in English And that's why he was able to substitute ";48"
for "THE" and this message started to make sense. And if you have time, you can complete
the decoding. Now, if our original Hidden Message Problem
was clearly ill-defined, let's now try to redefine it so that it would make sense even
for a computer scientist. How we would redefine it? Well, for various
biological signals, certain words appear surprisingly frequently in the text. For example, on this
slide, AATTT appears surprisingly frequently in a short text -- its unlikely that it would
happen by chance.
Then we formulate our first real Rosalind problem. The Frequent Words Problem is: "I'll
give you a string and an integer k, and you need to find all most frequent k-mers in Text,
which means all most frequent strings of length k in the Text.
Is the problem clear now? Let's ask Son. He feels better, but he is still not clear
because he does not know what exactly a "most frequent word" means.
I think he is a little bit picky today because it's easy to define what a most frequent word
means. A k-mer Pattern (a string of length k) is
a most frequent word in Text if no other k-mer is more frequent than Pattern.
And now even Son is satisfied and I want to thank Son for great help with development
of this lecture. Now, Son is satisfied but we should ask biologists
whether this problem actually makes sense. Remember, bioinformatics is about connecting
computational and experimental ideas. And if we check with biologists, it also looks
that they are quite satisfied with this problem. Indeed, replication is performed by DNA polymerase,
but to initiate replication, DNA polymerase needs a protein called DnaA.
DnaA binds to a short region (typically just a 9 nucleotide-long segment) within the replication
origin that is known as a DnaA box.
A DnaA box is actually the hidden message that we are looking for, and the DnaA box
actually tells the DnaA protein: bind right here! And the DnaA protein wants to see multiple
DnaA boxes to bind efficiently. So, it looks like we brought computational
people and biologists on the same page, and we are now ready to try to solve this problem.
Since it's the first problem at Rosalind, we expect a wide variety of different algorithms
proposed by you. The simplest algorithm probably is this one.
Start from the 1st k-mer in the Text, slide it through the Text and see how many identical
k-mers are present in the Text. How much time it takes? It takes time roughly
equal to |Text| ∙ k. But you need to do it for every k-mer in Text, and there are
roughly Text of them. So, the overall running time of this very
naïve algorithm is |Text2|∙ k. If |Text| is one million, you may have problems,
but in our case |Text| is typically small. The average length of the replication origin
is just 500, maybe 700 hundred nucleotides.
In this course, we will soon learn much more sophisticated algorithms: for example, some
of you may be amazed that the same task can be done incredibly fast. And we will cover
these algorithms in the class.
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.
© 2018 Coursera Inc. Tous droits réservés.
