2.6 Data Structures in Action
The previous sections introduced a fair amount of new Perl syntax and
capabilities. Now, let's see some of these new
capabilities in action.
2.6.1 The Problem of String Matching
It
is frequently important in biology to find the best possible match
for a short sequence in a longer sequence; for example, between an
oligonucleotide and the sequence of DNA that has been cloned in a YAC
or BAC. This match need not always be perfect; frequently, what is
important is to find the closest match available. This problem is
known in computer science as approximate string matching, and dynamic
programming is a popular technique used to compute the solution.The problem of string matching is to find a pattern, such as a
nucleotide or peptide fragment, in a longer text such as a chromosome
or protein.The problem of approximate string matching is to find a pattern in a
text in which the match might not be perfect. Perhaps a few of the
characters are different or missing; the problem is to find the best
match possible.
2.6.2 Genetic Variability and String Matching
Biologically,
approximate matches are of commanding importance. Evolutionary
changes between species can make genes with essentially the same
function collect a fair number of individual base changes; they may
even have acquired differences in exon structure. Even within a
species, individual base changes among groups in the population
(single nucleotide polymorphisms) are important causes of disease and
important clues in the discovery of disease-causing genes.Mutations tend to accumulate over time in noncoding regions of DNA;
mutations in coding regions tend to avoid altering critical regions
essential for the functioning of the gene (where mutations may be
fatal to the organism). Even a noncoding region may be critical to
the regulation of a gene and thus tend to resist mutations. As a
result, studying where mutations are not accumulating is often an
important clue to discerning the function and control of a gene and
its associated protein.Due to the redundancy of the genetic code, mutations in DNA may not
affect the coding of the associated protein. Other mutations may make
a change in a coded amino acid, but it may be an amino acid with
similar properties to the original amino acid; for instance, both
amino acids may be hydrophilic. Tracing these kinds of mutations is
another source of important information about the process of
mutation. It can give vital clues to the conservation of critical
coding regions and to the folding of proteins.Biologists will have no difficulty expanding upon the preceding brief
motivation for studying approximate string matching and other
techniques that find similarities between biological molecules. Many
standard laboratory techniques rely on the annealing of a molecule to
another molecule with similar, but not necessarily exact, structure.In the discussion that follows, you'll use your new
knowledge of complex data structures in Perl to implement an
algorithm that finds approximate matches of patterns in text, such as
DNA fragments in chromosomes or peptide fragments in proteins.The algorithm I present is an example of dynamic programming; it
relies on computing the entries to a matrix. |
لطفا منتظر باشید ...
