隐马尔可夫过程：理论与生物学应用

需积分: 10 79 浏览量更新于2024-07-18 收藏 3.18MB PDF 举报

"(Hidden) Markov Processes: Theory and Applications to Biology by M. Vidyasagar" 本书《隐藏马尔科夫过程：理论与生物应用》深入探讨了在生物学领域使用的隐藏马尔科夫模型（HMM，Hidden Markov Models）。自1966年引入统计学文献以来，HMMs在1970年代中期开始应用于语音识别，这是非数学背景下的早期应用之一。书中的内容涵盖了计算生物学的基础以及概率论和随机变量的理论。在第一章《计算生物学介绍》中，作者首先讨论了基因组的重要性，它是所有生命形式的基础。接着，书中解释了基因和蛋白质之间的关系，包括遗传密码的概念，即DNA如何编码蛋白质的信息。此外，本章还提到了基因寻找问题和蛋白质分类问题，这两个是生物信息学中的核心挑战。第二章《概率论和随机变量入门》详细介绍了随机变量的基础知识。从随机变量的定义和概率分布开始，逐步讲解期望值、两个概率度量之间的总变差距离。接着，书中讨论了多个随机变量，包括联合分布和边缘分布，以及独立性和条件分布的概念。Bayes'规则在此处得到阐述，它是概率推理的关键工具。此外，最大后验估计（MAP）和最大似然估计（MLE）作为参数估计的方法也被介绍，这些都是统计推断中的常用技术。第三章涉及可以取无限多个值的随机变量，这在处理连续随机变量时特别重要。书中还讨论了尾部概率估计，如马尔科夫不等式和切比雪夫不等式，这些是评估极端事件概率的有力工具。隐藏马尔科夫模型在生物学中的应用，特别是在基因预测和蛋白质功能分析方面，是本书的重点。通过使用HMMs，科学家能够识别基因序列中的模式，预测蛋白质结构和功能，以及解决其他生物序列分析问题。HMMs的动态编程算法，如维特比算法（Viterbi Algorithm），在序列比对和模式识别中起着关键作用。这本书不仅提供了隐藏马尔科夫模型的理论基础，还展示了如何将这些概念应用于实际的生物学问题中，对于生物信息学和计算生物学的研究者来说是一本宝贵的参考资料。通过学习这些内容，读者将能够理解和应用HMMs来解决复杂的生命科学问题。

text September 25, 2011

6 CHAPTER 1

As stated above, the two strands of the helix run in opposite directions.

Thus the 5’ end of one strand is opposite the 3’ end of the other strand.

Moreover, again as stated above, in order for the two strands to have a series

of hydrogen bonds, the two sides must satisfy the ‘reverse complementarity’

property. Thus, if one strand contains A (Adenine) in one location, the other

side must contain T (Thyamine). Similarly, C (Cytosine) and G (Guanine)

occur opposite each other.

The ‘genome’ of an organism is just a listing out, symbol by symbol, of

the sequence of nucleotides that makes up one strand of the DNA. Because

of reverse complementarity, if we know the listing of one strand, we know

unambiguously the listing of the other strand. Since DNA occurs in two

strands and the bases in each strand must ‘pair up’ according to reverse

complementarity, the length of a genome is speciﬁed in ‘base pairs.’ The

typical length of the genome varies depending upon the nature and com-

plexity of the organism. Viruses, which cannot survive on their own but

need a host in order to replicate, typically have genomes that several thou-

sand base pairs long. Bacteria, which are the simplest self-sustaining life

forms (meaning that they can reproduce on their own without a host, in

contrast to viruses) have genomes that are a few million base pairs long.

The mosquito has a genome that is about 300 million base pairs, the mouse

genome is about 2.4 billion base pairs, the human genome is about 3.3 bil-

lion base pairs, and ﬁnally, the rice genome has about 10 billion base pairs!

That last statistic, namely that the rice genome is three times as long as the

human genome, ought to dispel the idea that the length of the genome is

somehow monotonically related to the ‘intelligence’ of the organism.

The determination of the genome of organisms is one of the great triumphs

of experimental biology, because the genome is one of the most ‘unambigu-

ous’ representations of a life-form. See the ﬁrst chapter of [88] for an excel-

lent summary of the experimental methods and computational algorithms

involved in ‘sequencing’ and ‘assembling’ a genome, that is, determing the

string of symbols that comprise the genome. Moreover, it is noteworthy that

the genome is not an ‘analog’ representation of life, but is a ‘digital’ repre-

sentation, in the sense that the symbols at each location in the genome can

have only a ﬁnite number of possible values (four). In general, the genomes

of two exemplars of a species will have the same length. However, in the

case of organisms such as the HIV virus which reproduces itself very sloppily,

this statement is not always true. And of course, this statement is not valid

at all when organisms have been experimentally modiﬁed in a laboratory.

However, the genomes of two exemplars of an organism need not be iden-

tical. If the genome of an organism is 100% reproduced to create another

organism, the second one is called a ‘clone’ of the ﬁrst.

A draft of the human genome was determined and published simultane-

ously in February 2001 by two groups: The International Human Genome

Research Consortium (IHGSC) [60] and Celera Genomics [106], a private

company that subsequently went out of business. The human genome is

about 3.3 billion base pairs long. The exact length is not known precisely,

text September 25, 2011

INTRODUCTION TO COMPUTATIONAL BIOLOGY 7

and experiments are still under way to reﬁne the draft genome further.

In spite of its enormous length, it appears that there is a great deal of

redundancy in the human genome. The overlap between the human genome

and the mouse genome is about 80%, whereas between a human and a chim-

panzee (our nearest neighbour in the animal kingdom) is about 98%. Be-

tween two humans the overlap is still more striking. It is estimated that

the genome sequences of two humans will agree in about 99.9% of the loca-

tions, and diﬀer only in about 0.1%, or about 3 million base pairs. All that

distinguishes one human from another, be it height, weight, colour of eyes,

colour of hair, etc. can presumably be attributed to this tiny variation in

the genome (aside from environmental factors of course). These variations

from the ‘consensus’ human genome (see below) are called Single Nucleotide

Polymorphisms (SNPs), often pronounced as ‘snips’. Even ‘identical’ twins

will not have identiﬁcal genomes; rather, the overlap in such a case will be

about 99.99%, as opposed to 99.9% in the case of two unrelated humans. A

100% replication of a genome is known as a ‘clone’ as stated earlier. The

cloning of life forms is both a fascinating as well as a controversial subject.

It is widely accepted that there is indeed a ‘consensus’ human genome.

In other words, it is believed that at any given location, an overwhelming

majority of humans will have just one of the four nucleotides. Moreover,

in case there is a deviation from the consensus genome, even though there

are three variations possible in theory, in reality only one variation seems to

occur in an overwhelming majority of cases. It is not the case, for example,

that at a particular location about half of the population will have a T ,

another half will have a G, while A or C occur in a tiny fraction of the

population. It is also not the case that virtually all humans have, say, a T at a

particular location, whereas the symbols A, C, G occur among the remaining

small minority with roughly equal frequency. If at all there is a variation,

only one of the remaining three symbols will occur in almost all the rest of

humanity. To contrast the situation, there is no ‘consensus blood group’ for

example. While the O type blood is the most common, the percentage of the

population that has other blood types is still signiﬁcant. The draft human

genome published in February 2001 by Celera is actually the (approximate)

sequence of the DNA of no fewer than six diﬀerent individuals, not that of

just one person. Since the estimated error in the published draft (2% or so)

is considerably more than the variations amongst individuals (0.1% or so,

as mentioned above), this mixing up of DNA from diﬀerent individuals did

not matter. The above remarks about the existence of a consensus genome

apply also to other organisms.

As technology improves, we can aspire to a situation whereby it will be

both quick and inexpensive to determine the genome of every human on the

planet, or at least a large number of them. As stated above, it would be

wasteful to capture the DNA of a speciﬁc individual and sequence that. It

would be more eﬃcient to (i) determine the consensus genome very accu-

rately, and (ii) determine the SNP’s of an individual, that is, variations from

the consensus genome. It appears reasonable that Step (ii) above should be,

text September 25, 2011

8 CHAPTER 1

at least in principle, less expensive than an ab initio sequencing of the entire

genome of an individual, since the variations from the consensus genome are

expected in only 0.1% of the locations. The SNP proﬁle of an individual is

also known as the ‘genotype.’

One of the most exciting challenges in computational biology is correlating

an individual’s genotype with his/her ‘phenotype,’ for example, the person’s

propensity to disease, responsiveness to a drug or treatment regime, or even

potential adverse reactions to a drug. The current status is that in some very

speciﬁc situations, we know that a particular SNP causes a speciﬁc disorder.

Among the very ﬁrst disorders to be tied unambiguously to a speciﬁc SNP is

Sickle cell anemia, which causes red blood cells to be shaped like a crescent

(or a sickle), as opposed to the round shape of a normal red blood cell. It

was discovered that sickle cell anemia is caused by just one substitution:

The codon GAG that codes for glutamine gets replaced by GT G, which

codes for valine.

Thus exactly one SNP at just the right place in the

genome can cause sickle cell anemia. Other examples of genetic disorders are

Huntington Chorea and cystic ﬁbrosis. Cystic ﬁbrosis is in many ways well-

suited for study using computational techniques, because while the location

of the mutations that causes the disorder is well known, there are literally

hundreds of mutations that have been discovered thus far among patients

aﬄicted by this disorder. It would therefore be very interesting to correlate,

using computational techniques, the particular mutation with the particular

manifestation of the disorder. Unfortunately, most disorders are far more

complex, and cannot be related to the malfunction of one speciﬁc gene. The

paradigm ‘one gene, one protein, one function’ is not valid in many cases,

especially where disorders are involved.

1.2 GENES AND PROTEINS

1.2.1 The Genetic Code

As we have already seen, the genome of an organism is just an enormously

long string over the four-symbol nucleotide alphabet {A, C, G, T }. The

genome of an organism is the most ‘low level’ description of an organism.

Here the expression ‘low level’ is used to mean that it is the most basic de-

scription, and when we know that, we don’t actually know very much. One

can think of the genome as a kind of ‘raw data’ that needs to be turned into

‘information.’ This is one of the classic challenges of computational biology.

The next level of complexity in the genome arises from genes and proteins.

Proteins are the sustenance of life, and DNA must continually replicate itself

so that the production of proteins can go on uninterrupted. The DNA of

an organism consists in eﬀect of two parts: (i) the genes whose function is

to produce proteins, and (ii) the intergenic regions, often referred to ‘junk’

DNA. I myself dislike the expression ‘junk’ DNA. It seems to me that there

Codons are introduced later in this section.

text September 25, 2011

INTRODUCTION TO COMPUTATIONAL BIOLOGY 9

is a vast diﬀerence between saying ‘This stretch of DNA has no function’

and ‘This stretch of DNA has no known function.’ The ﬁrst is a statement

of fact, while the second is a statement about our ignorance. Actually the

second sentence accurately describes what we call ‘junk DNA.’ The situation

could change, and we may one day discover why there is ‘junk’ DNA. It is

also interesting why it is called ‘junk’ and not ‘trash,’ ‘garbage,’ or even

‘spam.’

Proteins were discovered as early as the beginning of the nineteenth cen-

tury, in fact much earlier than genes. Practically all the proteins discovered

at that time were essential dietary ingredients; for example, vitamins are

proteins or combinations of proteins. By the 1840’s it was already known

that every protein consists of a sequence of amino acids, which are twenty in

number. These twenty amino acids are denoted either by a single letter, or

by two or three letters. Just as the four nucleotides are the building blocks

of DNA, the twenty amino acids are the building blocks of proteins. Thus,

just we can think of the genome as a string over the four-symbol alphabet

of nucleotides, we can think of a protein as a string over the twenty-symbol

alphabet of amino acids. The listing out of a protein in terms of its sequence

of amino acids is called the primary structure. Thus we can think of

describing a protein in terms of its primary structure as being analogous to

describing an organism in terms of its genome. Both are the ‘lowest level’

descriptions, and additional work is needed to extract useful information in

either case. Typically a protein consists of several hundred, or perhaps a

few thousand, amino acids. At the other end, proteins consisting of as few

as ﬁfty amino acids are also known.

Once the double helix structure of DNA was discovered in 1953, the sci-

entiﬁc community attempted to understand how DNA gets converted to

proteins. The working hypothesis, which is by now quite universally ac-

cepted, states that ﬁrst the double-stranded DNA molecule is separated into

its two individual strands. Then particular stretches of DNA get cut out and

this forms the template for conversion to RNA. In the process, Thymine (T )

gets replaced by Uracil (U). RNA is a single-stranded molecule and is thus

somewhat unstable chemically. (However, double-stranded RNA has been

discovered recently). This process is known as ‘transcription.’ Then triplets

of RNA nucleotides A, C, G, U get converted into amino acids through a pro-

cess known as ‘translation.’ The entire hypothesis is labelled as ‘The Central

Dogma’ of biology. This much was understood by 1960, but what happened

next was still not clear. Figure 1.2.1 below depicts the central dogma.

Recall that the four nucleotides that make up DNA were discovered in

1929. The basis of the conversion of DNA to proteins, called the ‘genetic

code,’ was discovered in full only in the 1960’s. In 1961, Marshall Nirenberg

succeeded in showing that the triplet UUU produced the amino acid pheny-

laline. In quick succession he and his colleagues succeeded in showing that

several amino acids were produced by various triplets of nucleotides. It was

left to Hargobind Khorana to complete the picture by showing which triplet

of nucleotides produced which amino acid. Since there are 4

= 64 triplets

text September 25, 2011

10 CHAPTER 1

Figure 1.5 Central Dogma of Biology

(called ‘codons’) and only 20 amino acids, there had to be some redundancy.

Khorana further showed that each protein-coding RNA ended with one of

three sequences, called the stop codons, namely U AA, U AG, U GA. Fi-

nally, he also showed that every protein-coding RNA began with the ‘start’

codons AU G or GUG. However, while a stop codon cannot occur in the

middle of a protein sequence, a ‘start’ codon can also occur in the middle

of a protein, where it codes for the amino acid methionine. A key aspect of

Khorana’s work was that he was the ﬁrst one to synthesize oligonucleotides,

that is, to create artiﬁcially ‘arbitrary’ strings of nucleotides. This synthesis

technique allowed him to study the amino acids produced by all possible

triplets of nucleotides. In recognition of this seminal work, Nirenberg and

Khorana shared the Nobel Prize in Medicine in 1968, along with Robert

Holley, who discovered tRNA (translation RNA).

Figure 1.2.1 below depicts the genetic code in compact form. Strictly

speaking, RNA codons consist of triplets from the RNA alphabet {A, C, G, U}.

However, since the RNA sequence is obtained simply by replacing the symbol

T by the symbol U (ignoring the chemical signiﬁcance of such a substitution),

we can think of ‘codons’ as either triplets over the alphabet {A, C, G, T } or

over the alphabet {A, C, G, U }. We use both conventions interchangeably,

depending on convenience. Thus we can think of T AA, T AG, T GA as stop

codons, and of AT G, GT G as the start codons.

From the above table, it is clear that there is a great deal of subtlety in the

genetic code. If we think of the genetic code as a map from the 64-symbol set

{A, C, G, U }

into the twenty-one symbol set consisting of the twenty amino

acids plus the stop codon, then the structure of the map is not at all clear.

The size of the preimage of the various ‘output symbols’ (amino acids or stop

codon) ranges from a high of 6 for Leucine to a low of one for many amino

acids. Several persons have proposed various speculative explanations for

the structure of the genetic code, but until there is no universally accepted

explanation.

An interesting aspect of the above chain of discoveries is that physicists

played a central role in motivating much of this work. After the discovery

of individual nucleotides in 1929, the famous physicist Erwin Schr¨odinger

剩余287页未读，继续阅读

Alladins

粉丝: 1
资源: 57

隐马尔可夫过程：理论与生物学应用

陈双平研究：隐马尔可夫过程的多重分形谱及其应用

MATLAB HMM Toolbox应用与教程-Hidden Markov Model入门

BHMPs熵率的新型边界估计公式：陈双平、李军与 Zheng的研究

HMM.rar_hidden markov model _hidden model markov_markov processe

伯克利大学机器学习-7Hidden Markov models& graphical models

State Transition Factor of Three-state Markov Channels

【Advanced】Markov Chain Monte Carlo (MCMC) Fitting in MATLAB

鉴别式训练 Hidden Markov 模型：理论与实验

Matlab马尔科夫计算工具包：Hidden Markov Modelling应用

Spring MVC架构详解与配置指南：实现Web应用的高效开发

最新资源