This two-part course introduces the basic mathematical and programming principles that underlie much of Computer Science. Understanding these principles is crucial to the process of creating efficient and well-structured solutions for computational problems. To get hands-on experience working with these concepts, we will use the Python programming language. The main focus of the class will be weekly mini-projects that build upon the mathematical and programming principles that are taught in the class. To keep the class fun and engaging, many of the projects will involve working with strategy-based games. In part 2 of this course, the programming portion of the class will focus on concepts such as recursion, assertions, and invariants. The mathematical portion of the class will focus on searching, sorting, and recursive data structures. Upon completing this course, you will have a solid foundation in the principles of computation and programming. This will prepare you for the next course in the specialization, which will begin to introduce a structured approach to developing and analyzing algorithms. Developing such algorithmic thinking skills will be critical to writing large scale software and solving real world computational problems.
Modeling
Loading...
來自 Rice University 的課程
Principles of Computing (Part 2)
214 個評分
從本節課中
Modeling, Assertions, and Invariants
This week, we will explain the importance of modeling. We will also explore how to use assertions and invariants to ensure that our models are always consistent and correct.
與講師見面
Scott RixnerProfessor
Computer Science
Joe WarrenProfessor
Computer Science
Luay NakhlehAssociate Professor
Computer Science; Biochemistry and Cell Biology
[MUSIC]
Okay, so today I'm going to talk about
modeling, the importance of modeling in computer science.
And I'm going to illustrate it with a very important
example from my own research area, which is computational biology.
The example concerns the problem, a central problem in biology known
as the sequence alignment problem, or
more specifically, pair wise sequence alignment.
So, what is this problem?
Biologists often have this issue that they get a sequence, a DNA
sequence for a certain gene from human, and also from a different organism.
For example, they look at the human.
And take a sequence that looks like this, ACCT.
And they look at another organism, let's say, mouse.
They take, what we call a homologous sequence or the counterpart
of the sequence in mouse, and the sequence looks like ACTC.
Okay, let's see.
C another C here.
No, if you look at these two sequences, we,
the biologist says that I know these two sequences
evolve from a common ancestor, somehow a long time
ago when, when human and mouse had a common ancestor.
These two sequences came from one sequence.
They used to be one sequence millions of years ago.
Okay, so now again from human we have ACCT and here we have
ACTCC and they came from a common ancestor here.
Of course we have no record for this sequence, this one, again
this happened millions of years ago and we cannot just find this sequence
easily, we cannot find the sample in the, in nature, that we
can sequence and say, okay, this is how it used to be, right.
All right, so now the biologist is interested in the following problem.
Given these two sequences which biologists can easily get, I mean
we can easily today get DNA from human, and DNA from mouse.
They say I want you to align them.
Okay?
I want you to align them.
And through this alignment process, basically what
the biologist gets is reversing this process.
When I align these two sequences, we are
basically telling the biologist what type of mutations happened.
Now, when a biologist tells me this, that I want you to align these sequences.
I need to understand from the biologist first, is
that, why are the two sequences different, of different length.
The content is different also.
And what does the biologist mean by aligning them.
Okay?
So, when I talk to the biologist, the biologist says that by
aligning, I mean make them of equal length by inserting dashes in them.
Okay?
So, you can insert dash in any place in the sequence and align a letter with
a letter or a letter with a dash and you can make them of equal length.
So, for example, when I talk to the biologist, the
biologist might tell me, here's an example of an alignment.
ACCT-
ACTCC.
So, this way, basically, we are aligning this A with
A, C with C, C with T, T with C.
Because for this C, there's no letter, we ent, we insert a dash.
So, this is a possible alignment.
[BLANK_AUDIO]
Okay?
Now, if I look at this, what the biologist has told me,
then I can go to a biologist saying, is this an alignment?
[BLANK_AUDIO]
I inserted a dash, but here, between the A and C.
And it does, it does, it looks like an alignment because
it's of the same, both of them are the same length.
And I'm aligning a letter with a letter or a letter with a dash, right?
And biologist say, yes this is an alignment.
And then I say, is this an alignment?
And the biologist say, no
I don't like this because
this is meaningless.
Right?
I'm saying there was a, there was no letter here, no letter here.
And this is unnecessary to add.
So, biologist tells me that no, this is not an alignment.
Okay?
So now I start getting some information about
how to model the structure of an alignment.
So, to model the structure of an alignment, given two
sequences, basically I need to enter dashes in one or two
of the sequences so that I can make them aligned in
terms of, that is, they are both of the same length.
And when I enter these dashes, then I have to make the sequences of the same
length such that either a letter goes with a letter, or a dash with a letter.
But no dash with dash, okay?
So, this is a possible alignment, this is a possible alignment.
And this is the first step in, towards answering
the problem and solving the questions that the biologist is
interested in, which is how do we model an alignment,
what is the actual mathematical object that captures an alignment.
And in this case, it is we can formalize it very cleanly, mathematically by
saying, given two sequences, you can enter dashes in any of them or both.
Such that you make them of the same length.
And such that no dash goes with a dash, either
a letter with a letter or a dash with a letter.
And, of course, you cannot change the order
of the letters in any of the sequences.
So I cannot take ACCT and make it ACTC, for example.
All right?
So now, the first phase of, of modeling here was to get a notion of feasibility.
What is a feasible alignment versus what's not feasible.
This is not allowed.
The biologist doesn't like something like this.
So, now that I understand from a biologist what he or she wants
from me in terms of what is an alignment, I can look at this.
Now we can use mathematical skills to say, okay,
what is the number of such possible feasible alignments?
And I'm not going to show the number here.
But believe me, the number is going to be very large.
Right?
In the sense that if you give me a sequence of length four
and a sequence of length five, there are many, many ways of aligning them.
For example, one that you are not seeing here, is, for is ACCT.
They all go with dash here, and ACTCC, they all go with dashes here.
This is another possible alignment.
Okay?
It is feasible the, both of the same length.
A letter goes with a dash or a letter with a letter.
Nothing is wrong with it.
And I can keep adding more and more.
So the first step of modelling the feasibility of an alignment.
What is an alignment?
That is fine.
All right?
And using mathematical tools now I can reason about what is the number.
Once I reason about the number and find it's very large.
Now I understand I need also a way to choose among these.
So I can tell the biologist, here's an alignment.
Here's an alignment.
Here's an alignment.
And I can keep listing them.
But the biologist says, for example, I don't like this.
Or the biologist might say, I don't like this.
Now we have again to go back to the modeling
phase, which is to say, why don't you like this?
Or, why don't you like this?
This is a modeling question.
Because if a biologist tells me that they like this
but not like this, I have now to start doing
a mathematical reasoning about his so that I turn that
like and dislike, I turn it into some mathematical measure.
Say, I will define a measure that will
give a better value to this, than this, okay?
And once we do this, now we can turn to the algorithmic question, and
say, now that I have a measure, that gives a score to each possible alignment.
Now I'm interested in an algorithm that will find,
of all possible alignments, the one that maximizes the score.
Okay, and here, just to give an example of one what such a score might be.
And this is a real example, I mean, this is what a biologist might use.
For example here, for the, for the case of DNA, you can basically
describe such a, scoring mechanism by a 5 by 5 matrix.
And, every entry here is going to tell us what is the score or
penalty of putting a letter with a letter or a dash with a letter.
So, for example, the biologist might say, I, I, I like
alignments that always match the same letter with the same letters.
Like A with A, C with C, T with T, G with G.
In terms of modeling, it means that I should give
very high score to these cases, like ten, ten, ten, ten.
The biologists will tell me that because
of evolution and mutation can change the letter,
that the biologist is willing to accept T going with C, for example, all right.
But they will again still pre, pre, prefer that the sequence are written like this.
So, in that case, we can give this is A, A, A going with C, for example, a score
that's lower than ten, we can give it four, four, four and so on, okay.
And we can use it as symmetric metrics and we can give the same thing.
Then the biologists might say, you know, I
don't like too many dashes, I'm going to penalize it.
I'm going to see if I put dashes, the more dashes you put,
the lower the score should get, so we have to penalize these things.
For example, saying that if you put any letter with
a dash you penalize it by three points, for example.
[NOISE] And in some sense, this is minus infinity.
I'm not going to allow you to put a dash with a dash.
If you put it.
The score of that is very bad.
That we are not going to accept that alignment.
Okay?
So now, this is the second phase of the modelling.
Which is, how do I get a score for an alignment?
Or how do I evaluate an alignment whether it is good or not?
By going through the modelling.
By saying, the biologist has given, been
giving me information about, you know, what,
what do they like about A with A, or don't like about dash with C?
And I turn it into a mathematical object.
because once I have this, now I can say, what is the score of this alignment?
Well, the answer is, A with A, that scores ten.
C with C scores ten.
T with C scores four.
T over C scores four.
Dash over C scores minus three.
And if I use an additive measure, I say it's 20, 28, minus 3, 25.
Okay, so now I'm going through this modeling, I
have been going through back and forth with a biologist.
Taken the notion of an alignment that the biologist was mentioning.
It's going through modeling.
I understand what is a feasible alignment, what's not feasible, then given all the
possible feasible alignment, through modeling, I have
some, some mechanism to score this alignment.
And then the last step I would go through with algorithmic development phase.
Where I can develop an algorithm that will find, of all the possible,
feasible alignments, and given the scoring scheme, the one that maximizes the score.
Okay.
So this is an example that illustrates the importance of modeling.
I couldn't have gone to solve the problem for the biologist if I didn't go through
this entire process of modelling what is in
alignment, what is fine, what is not fine.
How do I distinguish among the fine alignments or the feasible ones?
And this process of modeling is very mathematical in nature.
And this is why we have been teaching you math, to illustrate, to,
to be able to use this mathematical tools to go through this process
