Page 410 - Discrete Mathematics and Its Applications

6.1 The Basics of Counting 389

enable living process. For our purposes, we give only the briefest description of how DNA and
RNA encode genetic information.
DNA molecules consist of two strands consisting of blocks known as nucleotides. Each
nucleotide contains subcomponents called bases, each of which is adenine (A), cytosine (C),
guanine (G), or thymine (T). The two strands of DNA are held together by hydrogen bonds
connecting different bases, with A bonding only with T, and C bonding only with G. Unlike
DNA, RNA is single stranded, with uracil (U) replacing thymine as a base. So, in DNA the
possible base pairs areA-T and C-G, while in RNA they areA-U, and C-G. The DNA of a living
creature consists of multiple pieces of DNA forming separate chromosomes.A gene is a segment
of a DNA molecule that encodes a particular protein. The entirety of genetic information of an
organism is called its genome.
Sequences of bases in DNA and RNA encode long chains of proteins called amino acids.
There are 22 essential amino acids for human beings. We can quickly see that a sequence of at
least three bases are needed to encode these 22 different amino acid. First note, that because
there are four possibilities for each base in DNA, A, C, G, and T, by the product rule there are
3
2
4 = 16 < 22 different sequences of two bases. However, there are 4 = 64 different sequences
of three bases, which provide enough different sequences to encode the 22 different amino acids
(even after taking into account that several different sequences of three bases encode the same
amino acid).
5
The DNA of simple living creatures such as algae and bacteria have between 10 and 10 7
links, where each link is one of the four possible bases. More complex organisms, such as in-
8
sects, birds, and mammals have between 10 and 10 10 links in their DNA. So, by the product
rule, there are at least 4 10 5 different sequences of bases in the DNA of simple organisms and at
least 4 10 8 different sequences of bases in the DNA of more complex organisms. These are both
Soon it won’t be that
costly to have your own incredibly huge numbers, which helps explain why there is such tremendous variability among
genetic code found. living organisms. In the past several decades techniques have been developed for determining
the genome of different organisms. The first step is to locate each gene in the DNA of an or-
ganism. The next task, called gene sequencing, is the determination of the sequence of links
on each gene. (Of course, the specific sequence of kinks on these genes depends on the partic-
ular individual representative of a species whose DNA is analyzed.) For example, the human
genome includes approximately 23,000 genes, each with 1,000 or more links. Gene sequencing
techniques take advantage of many recently developed algorithms and are based on numerous
new ideas in combinatorics. Many mathematicians and computer scientists work on problems
involving genomes, taking part in the fast moving fields of bioinformatics and computational
biology. ▲

We now introduce the sum rule.

THE SUM RULE If a task can be done either in one of n 1 ways or in one of n 2 ways, where
none of the set of n 1 ways is the same as any of the set of n 2 ways, then there are n 1 + n 2
ways to do the task.

Example 12 illustrates how the sum rule is used.
EXAMPLE 12 Suppose that either a member of the mathematics faculty or a student who is a mathematics major
is chosen as a representative to a university committee. How many different choices are there
for this representative if there are 37 members of the mathematics faculty and 83 mathematics
majors and no one is both a faculty member and a student?

Solution: There are 37 ways to choose a member of the mathematics faculty and there are 83
ways to choose a student who is a mathematics major. Choosing a member of the mathematics
faculty is never the same as choosing a student who is a mathematics major because no one is