Adapting Sequencing for Spectra with Errors

Loading...

En provenance du cours de University of California San Diego

Genome Sequencing (Bioinformatics II)

143 notes

University of California San Diego

Genome Sequencing (Bioinformatics II)

143 notes

Cours 2 sur 7 dans Specialization Bioinformatics

You may have heard a lot about genome sequencing and its potential to usher in an era of personalized medicine, but what does it mean to sequence a genome? Biologists still cannot read the nucleotides of an entire genome as you would read a book from beginning to end. However, they can read short pieces of DNA. In this course, we will see how graph theory can be used to assemble genomes from these short pieces. We will further learn about brute force algorithms and apply them to sequencing mini-proteins called antibiotics. In the first half of the course, we will see that biologists cannot read the 3 billion nucleotides of a human genome as you would read a book from beginning to end. However, they can read shorter fragments of DNA. In this course, we will see how graph theory can be used to assemble genomes from these short pieces in what amounts to the largest jigsaw puzzle ever put together. In the second half of the course, we will discuss antibiotics, a topic of great relevance as antimicrobial-resistant bacteria like MRSA are on the rise. You know antibiotics as drugs, but on the molecular level they are short mini-proteins that have been engineered by bacteria to kill their enemies. Determining the sequence of amino acids making up one of these antibiotics is an important research problem, and one that is similar to that of sequencing a genome by assembling tiny fragments of DNA. We will see how brute force algorithms that try every possible solution are able to identify naturally occurring antibiotics so that they can be synthesized in a lab. Finally, you will learn how to apply popular bioinformatics software tools to sequence the genome of a deadly Staphylococcus bacterium that has acquired antibiotics resistance.

À partir de la leçon

Week 4: From Ideal to Real Spectra for Antibiotics Sequencing

<p>Welcome to Week 4 of class!</p> <p>Last week, we discussed how to sequence an antibiotic peptide from an ideal spectrum. This week, we will see how to develop more sophisticated algorithms for antibiotic peptide sequencing that are able to handle spectra with many false and missing masses.</p>

Adapting Sequencing for Spectra with Errors 7:40

From 20 to More than 100 Amino Acids 2:20

The Spectral Convolution Saves the Day 6:02

The Truth About Spectra 2:20

Rencontrer les enseignants

Pavel Pevzner
Professor
Department of Computer Science and Engineering
Phillip Compeau
Visiting Researcher
Department of Computer Science & Engineering

OK so, at the end of this last section, I canceled our party,

and said that we have this algorithm that

works really well in practice on theoretical spectra.

But the issue is going to be that when we move to experimental spectra,

we're going to have issues

because these experimental spectra often produce errors.

Here are the theoretical

and an experimental spectrum for the peptide NQEL.

The theoretical spectrum is on the top, and then

we're giving you a hypothetical experimental spectrum for the same peptide.

This experimental spectrum highlights a couple of different ways

that the experimental spectrum can be flawed.

It can detect “false” masses.

These are masses that are present in the experimental spectrum

but that don't correspond to real masses in the theoretical spectrum.

Examples are 99 and 299 here.

We also have “missing” masses.

They're masses that are in the theoretical spectrum of the

correct peptide but that don't actually

get produced in the experimental spectrum,

so they're “missing”.

This is a problem, because our current implementation,

in order for it to consider a peptide

correct, the peptide's theoretical spectrum has to exactly match

the experimental spectrum that we have, and that's clearly not the case here.

The question then is what do we do.

What we're going to do is, instead of having to match the spectrum exactly,

we're going to instead “score” a peptide based off

of how similar it is to the experimental spectrum.

For example, here,

the theoretical spectrum of NQEL is still pretty

similar to the experimental spectrum that we have.

Notice that it shares 11 masses.

So, we're going to say that the score then,

of NQEL, with this experimental spectrum, is equal to 11.

We need to use this scoring function

to say certain peptides are better than others

and to use this to modify the branch and bound algorithm

that we have in order to make it a little bit better.

The idea that I want to use here is

similar to something called a “cut” in a golf tournament.

Now I'm a huge golf fan, so maybe I'm just partial to this idea,

but I thought it fit it pretty well.

What the cut does, is it reduces the field to

only the players that are deemed to be in contention for the tournament.

So, if there are players, that are not doing too

well after a couple of rounds, then, they say,

OK, well, we're just going to let them go home.

And, we want to have the tournament only for the

players who have a chance of actually winning the tournament.

Here's a hypothetical leaderboard,

and we may say, in this hypothetical small tournament that

we want to keep the top three players on the leaderboard.

Keeping in mind that low golf scores are good, we put the cut line here.

But this would be unfair to this golfer, right, because

they're tied with the third place golfer, and so we

need to say, well we keep the top three players…

…as well as ties.

So, keep the top three players “with ties”.

This is going to motivate the bound step that we do.

So, after this cut, we have four players remaining.

The new idea is, we're going to call it LeaderboardCyclopeptideSequencing.

How it works is that we're going to start off with a zero peptide.

So, this is an empty string, essentially.

And then we're going to extend

each peptide on the leaderboard

in each of 18 possible different directions, so we

add each of the 18 different amino acid masses

to the peptides that we have, currently, in the leaderboard, which

when we begin is empty, or it has just the zero peptide.

Then we're going to have this “cut” step, which is the

new “bound step”, and it's going to cut the low scoring peptide, so it says:

Assign everything a score,

see what the score of every peptide is, and then cut the low scoring ones.

Get them out of there so that we can

prevent the number of solutions that we consider from growing,

and so that we can keep only the high scoring peptides.

So, we're going to keep the top N peptides “with ties”.

Then, the next step is going to say OK, we'll update the “leader peptide”.

We're going to keep track of

what the leader peptide should be,

and, if there's

a higher scoring peptide that we can find on the leaderboard,

so if something moves up and becomes a higher scoring peptide,

and its mass is equal to that parent mass, that we can detect.

By the “parent mass” I mean

We said that we're always going to be able to

know in advance what the correct mass of the entire peptide should be.

So, we always want to check if these candidate solutions

that we have have a mass that's equal to that

total mass.

And then, we're going to eliminate any

peptides whose mass is going to grow too big.

So, if their mass exceeds the parent mass,

then, we're not going to want to expand them any more, because

their mass is too big, and we want to get rid of them, too.

So, once we do these steps, we're just

going to iterate these steps over and over again.

So, we have a branch step, and then, a bound step.

And then, we have an “update step”, where we say, is there a leader?

And can we get rid of

anything whose mass has gotten too big?

At the end, after we go through this

procedure, we're going to branch and bound and branch and bound,

it's actually going to guarantee to always have an empty leaderboard at the end.

So, at step 6, after we go through

steps 2 through 5, we're going to have an empty leaderboard.

And then, at that time we return, what is our leader?

What's the best peptide that we've encountered so far?

So, we have

this updated method.

But, I do want to give you the warning, that it's what's called a “heuristic”.

Because it's dealing with high scoring peptides, there's a chance that

there is an initially low-scoring peptide that winds up eventually being

the highest scoring peptide, so that eventually would be our leader,

but because we cut it in an early stage, because, we said it's

not in the top however many N peptides, then we throw it out.

And so there is a possibility that we throw out

the correct peptide, or what will eventually become the correct peptide,

at the expense of having a quick method.

And so for this reason it's a heuristic.

Let's test it though, because remember, we're considering

how well these algorithms work in practice.

So, here is a hypothetical spectrum. It has 10% false and missing masses.

I'll highlight where

the false and missing masses are.

So, here are the false masses, and here are the missing masses.

Now, we're not going to know which of

these are false and missing to begin with.

In particular, we're not going to have the missing masses present.

That's the whole point.

They're not present in the experimental spectrum.

So, we'll have this picture, but we won't

know which of the masses should be green.

And then, we say, let's run our algorithm, let's run

our leaderboard algorithm, on this hypothetical data set, and see what it

churns out.

And so it returns the, the correct Tyrocidine B1

peptide, which is where this came from, so we're happy.

Then we say, well, maybe 10% false and

missing masses, maybe that was a little bit optimistic.

So, let's introduce a slightly noisier Tyrocidine B1

spectrum that has 25% false and missing masses.

And again, I'll show you (even though we won't know this)

I'll show you where the false and missing masses are,

so you can believe me.

And, we can say, we won't know which masses are missing.

Now, when we run that same algorithm, on this noisier spectrum.

We're going to see that

the peptide that it produces

is actually not Tyrocidine B1. It's close, but instead of the

correct amino acid here, It's been replaced with an AD, so this is bad.

In this case, we wouldn't be able to reconstruct the correct peptide.

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.

Télécharger dans l'App Store

Disponible sur Google Play