National Academies Press: OpenBook
« Previous: Combinatorial Assemblies
Suggested Citation:"Other Combinatorial Structures." National Research Council. 1995. Calculating the Secrets of Life: Contributions of the Mathematical Sciences to Molecular Biology. Washington, DC: The National Academies Press. doi: 10.17226/2121.
×
Page 142
Suggested Citation:"Other Combinatorial Structures." National Research Council. 1995. Calculating the Secrets of Life: Contributions of the Mathematical Sciences to Molecular Biology. Washington, DC: The National Academies Press. doi: 10.17226/2121.
×
Page 143

Below is the uncorrected machine-read text of this chapter, intended to provide our own search engines and external engines with highly rich, chapter-representative searchable text of each book. Because it is UNCORRECTED material, please consider the following text as a useful but insufficient proxy for the authoritative book pages.

CALIBRATING THE CLOCK: USING STOCHASTIC PROCESSES TO MEASURE THE RATE OF EVOLUTION 142 There are many uses to which such total variation estimates can be put. In essence, functionals of the dependent process that depend mainly on the small component counts (that is, on components of size o(n)) are well approximated by the corresponding functionals of the independent process, which are often much easier to analyze. A typical example shows that the total number of components in such a structure asymptotically has a normal distribution, with mean and variance θκ log n . A corresponding functional central limit theorem follows by precisely the same methods. In addition, these estimates lead to bounds on the distances between the laws of such functionals. Some examples that illustrate the power of this approach can be found in Arratia and Tavaré (1992) and Arratia et al. (1993). Other Combinatorial Structures The strategy employed for assemblies also works for other combinatorial structures, including multisets and selections. We focus just on the multiset case. To build such structures, which are now unlabeled, imagine a supply of mj types of irreducible component of weight j, and build an object of total weight n by choosing components with replacement. The number N(a) of structures of weight n having aj components of size j = 1,2,. . .,n is (5.34) and the total number of structures of weight n is p(n) = ∑aN(a). A random multiset of size n has aj components of size j with probability (5.35) The ingredient common to assemblies and multisets is the fact that

CALIBRATING THE CLOCK: USING STOCHASTIC PROCESSES TO MEASURE THE RATE OF EVOLUTION 143 but the approximating independent random variables {Zi} are no longer Poisson, but rather negative binomial with parameters mi and xi: (5.36) valid for 0 < x < 1. In the θ-biased case, the Zi are negative binomial with parameters mi and θxi, for any θ < x-1. The most studied example in this setting concerns the factorization of a random monic polynomial over the finite field GF(q) with q elements. The components of size i are precisely the irreducible factors of degree i, there being of them. The function µ(·) is the Möbius function: µ(k) = −l or 1 according to whether k is the product of an odd or even number of distinct prime factors, and µ(k) = 0 if k is divisible by the square of a prime. The logarithmic condition (5.37) is satisfied by random polynomials with κ = 1 and y = q. For this logarithmic class the total variation estimates (5.32) and (5.33) apply once more (with appropriate modification for the θ-biased case), and the techniques described at the end of the previous section can then be used to study the behavior of many interesting functionals. In particular, examples describing the functional central limit theorem, with error estimates, for the random polynomial case, can be found in Arratia et al. (1993).

Next: The Large Components »
Calculating the Secrets of Life: Contributions of the Mathematical Sciences to Molecular Biology Get This Book
×
Buy Paperback | $80.00
MyNAP members save 10% online.
Login or Register to save!
Download Free PDF

As researchers have pursued biology's secrets to the molecular level, mathematical and computer sciences have played an increasingly important role—in genome mapping, population genetics, and even the controversial search for "Eve," hypothetical mother of the human race.

In this first-ever survey of the partnership between the two fields, leading experts look at how mathematical research and methods have made possible important discoveries in biology.

The volume explores how differential geometry, topology, and differential mechanics have allowed researchers to "wind" and "unwind" DNA's double helix to understand the phenomenon of supercoiling. It explains how mathematical tools are revealing the workings of enzymes and proteins. And it describes how mathematicians are detecting echoes from the origin of life by applying stochastic and statistical theory to the study of DNA sequences.

This informative and motivational book will be of interest to researchers, research administrators, and educators and students in mathematics, computer sciences, and biology.

  1. ×

    Welcome to OpenBook!

    You're looking at OpenBook, NAP.edu's online reading room since 1999. Based on feedback from you, our users, we've made some improvements that make it easier than ever to read thousands of publications on our website.

    Do you want to take a quick tour of the OpenBook's features?

    No Thanks Take a Tour »
  2. ×

    Show this book's table of contents, where you can jump to any chapter by name.

    « Back Next »
  3. ×

    ...or use these buttons to go back to the previous chapter or skip to the next one.

    « Back Next »
  4. ×

    Jump up to the previous page or down to the next one. Also, you can type in a page number and press Enter to go directly to that page in the book.

    « Back Next »
  5. ×

    To search the entire text of this book, type in your search term here and press Enter.

    « Back Next »
  6. ×

    Share a link to this book page on your preferred social network or via email.

    « Back Next »
  7. ×

    View our suggested citation for this chapter.

    « Back Next »
  8. ×

    Ready to take your reading offline? Click here to buy this book in print or download it as a free PDF, if available.

    « Back Next »
Stay Connected!