Poloidal–toroidal decomposition

2013-11-20T18:07:47Z

128.100.109.30: /* Poloidal and toroidal vector fields */ symbol error

'''DNA sequencing theory''' is the broad body of work that attempts to lay analytical foundations for determining the order of specific [[nucleotide]]s in a sequence of [[DNA]], otherwise known as [[DNA sequencing]]. The practical aspects revolve around designing and optimizing sequencing projects (known as "strategic genomics"), predicting project performance, troubleshooting experimental results, characterizing factors such as sequence bias and the effects of software processing algorithms, and comparing various sequencing methods to one another. In this sense, it could be considered a branch of [[systems engineering]] or [[operations research]]. The permanent archive of work is primarily mathematical, although numerical calculations are often conducted for particular problems too. DNA sequencing theory addresses ''physical processes'' related to sequencing DNA and should not be confused with theories of analyzing resultant DNA sequences, e.g. [[sequence alignment]]. Publications<ref name="waterman95">{{cite book |last=Waterman |first=Michael S. |authorlink=Michael Waterman |year=1995 |title=Introduction to Computational Biology |publisher=Chapman and Hall/CRC |location=Boca Raton |isbn=0-412-99391-0}}</ref> sometimes do not make a careful distinction, but the latter are primarily concerned with [[algorithm]]ic issues. Sequencing theory is based on elements of [[mathematics]], [[biology]], and [[systems engineering]], so it is highly interdisciplinary. The subject may be studied within the context of [[computational biology]].

==Theory and sequencing strategies==

===Sequencing as a covering problem===

All mainstream methods of [[DNA sequencing]] rely on reading small fragments of DNA and subsequently reconstructing these data to infer the original DNA target, either via [[sequence assembly|assembly]] or [[Sequence alignment|alignment]] to a reference. The [[abstraction]] common to these methods is that of a mathematical [[Cover (topology)|covering problem]].<ref name="hall">{{cite book |last=Hall |first=P. |year=1988 |title=Introduction to the Theory of Coverage Processes |publisher=Wiley |location=New York |isbn=0-471-85702-5}}</ref> For example, one can imagine a line segment representing the target and a subsequent process where smaller segments are "dropped" onto random locations of the target. The target is considered "sequenced" when adequate coverage accumulates (e.g., when no gaps remain).

The abstract properties of covering have been studied by mathematicians for over a century.<ref name="solomon">{{cite book |last=Solomon |first=H. |year=1978 |title=Geometric Probability |publisher=Society for Industrial and Applied Mathematics |location=Philadelphia |isbn=0-898-71025-1}}</ref> However, direct application of these results has not generally been possible. Closed-form mathematical solutions, especially for probability distributions, often cannot be readily evaluated. That is, they involve inordinately large amounts of computer time for parameters characteristic of [[DNA sequencing]]. Stevens' configuration is one such example.<ref name="stevens">{{cite journal |author=Stevens WL |year=1939 |title=Solution to a Geometrical Problem in Probability |journal=Annals of Eugenics |volume=9 |pages=315–320}}</ref> Results obtained from the perspective of [[pure mathematics]] also do not account for factors that are actually important in sequencing, for instance detectable overlap in sequencing fragments, double-stranding, edge-effects, and target multiplicity. Consequently, development of sequencing theory has proceeded more according to the philosophy of [[applied mathematics]]. In particular, it has been problem-focused and makes expedient use of approximations, simulations, etc.

===Early uses derived from elementary probability theory===

The earliest result was actually borrowed directly from elementary probability theory. If we model the above process and take <math>L</math> and <math>G</math> as the fragment length and target length, respectively, then the probability of "covering" any given location on the target ''with one particular fragment'' is <math>L / G</math>. (Note that this presumes <math>L \ll G</math>, which is valid for many, though not all sequencing scenarios). The probability of '''not''' covering a given location on the target is therefore <math>1 - L / G</math> for a single fragment and <math>\left[1 - L / G\right]^N</math> for <math>N</math> fragments. The probability of covering a given location on the target with ''at least one'' fragment is therefore

:<math>P = 1 - \left[1 - \frac{L}{G}\right]^N.</math>

This equation was first used to characterize plasmid libraries,<ref name="clarkecarbon">{{cite journal |author=Clarke L, Carbon J |year=1976 |title=A colony bank containing synthetic Col-El hybrid plasmids representative of the entire E. coli genome |journal=Cell |volume=9 |issue=1 |pages=91–99 |doi=10.1016/0092-8674(76)90055-6 |pmid=788919 }}</ref> but is often more useful in a modified form. For most projects <math>N \gg 1</math>, so that, to a good degree of approximation

:<math>\left[1 - \frac{L}{G}\right]^N \sim \exp(-NL/G),</math>

where <math>R = NL/G</math> is called the ''redundancy''. Note the significance of redundancy as representing the average number of times a position is covered with fragments. Note also that in considering the covering process over all positions in the target, this probability is identical to the [[expected value]] of the random variable <math>C</math>, which represents the fraction of the target coverage. The final result,

:<math>E\langle C \rangle = 1 - e^{-R},</math>

remains in widespread use as a "[[Back-of-the-envelope calculation|back of the envelope]]" estimator and predicts that coverage for all projects evolves along a universal curve that is a function only of the redundancy.

===Lander-Waterman theory===

In 1988, [[Eric Lander]] and [[Michael Waterman]] published an important paper<ref name="landerwaterman">{{cite journal |author=[[Eric Lander|Lander ES]], [[Michael Waterman|Waterman MS]] |year=1988 |title=Genomic mapping by fingerprinting random clones: a mathematical analysis |journal=Genomics |volume=2 |issue=3 |pages=231–239 |doi=10.1016/0888-7543(88)90007-9 |pmid=3294162 }}</ref> examining the covering problem from the standpoint of gaps. Although they focused on the so-called [[Gene mapping|mapping problem]], the abstraction to sequencing is much the same. They furnished a number of useful results that were adopted as the standard theory from the earliest days of "large-scale" genome sequencing.<ref name="fleischmann">{{cite journal |author=Fleischmann RD, ''et al.'' |year=1995 |title=Whole-genome random sequencing and assembly of haemophilus influenzae Rd |journal=Science |volume=269 |issue=5223 |pages=496–512 |doi=10.1126/science.7542800 |pmid=7542800 |bibcode = 1995Sci...269..496F }}</ref> Their model was also used in designing the [[Human Genome Project]] and continues to play an important role in DNA sequencing.

Ultimately, the main goal of a sequencing project is to close all gaps, so the "gap perspective" was a logical basis of developing a sequencing model. One of the more frequently used results from this model is the expected number of [[contig]]s, given the number of fragments sequenced. If one neglects the amount of sequence that is essentially "wasted" by having to detect overlaps, their theory yields

:<math>E\langle contigs \rangle = N e^{-R}.</math>

In 1995, Roach<ref name="roach95">{{cite journal |author=Roach JC |year=1995 |title=Random subcloning |journal=Genome Research |volume=5 |issue=5|pages=464–473 |doi=10.1101/gr.5.5.464 |pmid=8808467 }}</ref> published improvements to this theory, enabling it to be applied to sequencing projects in which the goal was to completely sequence a target genome. [[Michael Christopher Wendl|Michael Wendl]] and [[Bob Waterston]]<ref name="wendl02">{{cite journal |author=[[Michael Christopher Wendl|Wendl MC]], [[Bob Waterston|Waterston RH]] |year=2002 |title=Generalized gap model for bacterial artificial chromosome clone fingerprint mapping and shotgun sequencing |journal=Genome Research |volume=12 |issue=12 |pages=1943–1949 |doi=10.1101/gr.655102 |pmid=12466299 |pmc=187573}}</ref> confirmed, based on Stevens' method,<ref name="stevens"/> that both models produced similar results when the number of contigs was substantial, such as in low coverage mapping or sequencing projects. As sequencing projects ramped up in the 1990s, and projects approached completion, low coverage approximations became inadequate, and the exact model of Roach was necessary. However, as the cost of sequencing dropped, parameters of sequencing projects became easier to directly test empirically, and interest and funding for strategic genomics diminished

The basic ideas of Lander–Waterman theory led to a number of additional results for particular variations in mapping techniques.<ref name="arratia">{{cite journal |author=[[Richard Arratia|Arratia R]], ''et al.'' |year=1991 |title=Genomic mapping by anchoring random clones: a mathematical analysis |journal=Genomics |volume=11 |pages=806–827 |issue=4 |doi=10.1016/0888-7543(91)90004-X |pmid=1783390 }}</ref><ref name="port">{{cite journal |author=Port E, ''et al.'' |year=1995 |title=Genomic mapping by end-characterized random clones: a mathematical analysis |journal=Genomics |volume=26 |pages=84–100 |issue=1 |doi=10.1016/0888-7543(95)80086-2 |pmid=7782090 }}</ref><ref name="zhang">{{cite journal |author=Zhang MQ, Marr TG |year=1993 |title=Genome mapping by nonrandom anchoring: a discrete theoretical analysis |journal=[[Proceedings of the National Academy of Sciences]] |volume=90 |issue=2 |pages=600–604 |doi=10.1073/pnas.90.2.600 |bibcode = 1993PNAS...90..600Z }}</ref> However, technological advancements have rendered mapping theories largely obsolete except in organisms other than highly studied model organisms (e.g., yeast, flies, mice, and humans).

===Parking strategy===

The parking strategy for sequencing resembles the process of parking cars along a curb. Each car is a sequenced clone, and the curb is the genomic target.<ref name="roach2000">{{cite journal |author=Roach JC, ''et al.'' |year=2000 |title=Parking strategies for genome sequencing |doi=10.1101/gr.10.7.1020 |journal=Genome Research |volume=10 |issue=7 |pages=1020–1030 |pmid=10899151 |pmc=310895}}</ref> Each clone sequenced is screened to ensure that subsequently sequenced clones do not overlap any previously sequenced clone. No sequencing effort is redundant in this strategy. However, much like the gaps between parked cars, unsequenced gaps less than the length of a clone accumulate between sequenced clones. There can be considerable cost to close such gaps.

===Pairwise end-sequencing===

In 1995, Roach ''et al.''<ref name="roach1995b">{{cite journal |author=Roach JC, Boysen C, Wang K, [[Leroy Hood|Hood L]] |year=1995 |title=Pairwise end sequencing: a unified approach to genomic mapping and sequencing |journal=Genomics |volume=26 |issue=2 |pages=345–353 |doi=10.1016/0888-7543(95)80219-C |pmid=7601461}}</ref> proposed and demonstrated through simulations a generalization of a set of strategies explored earlier by Edwards and Caskey.<ref name="edwards91">{{cite book |author=Edwards, A.; Caskey, T. |year=1991 |title=Closure strategies for random DNA sequencing |publisher=A Companion to Methods in Enzymology |volume=3 |pages=41–47}}</ref> This [[Shotgun_sequencing#Whole_genome_shotgun_sequencing|whole-genome sequencing]] method became immensely popular as it was championed by Celera and used to sequenced several model organisms before Celera applied it to the human genome. Today, most sequencing projects employ this strategy, often called paired end sequencing.

==Post Human Genome Project advancements==

The physical processes and protocols of DNA sequencing have continued to evolve, largely driven by advancements in bio-chemical methods, instrumentation, and automation techniques. There is now a wide range of problems that [[DNA sequencing]] has made in-roads into, including [[metagenomics]] and [[Cancer Genome Project|medical (cancer) sequencing]]. There are important factors in these scenarios that classical theory does not account for. Recent work has begun to focus on resolving the effects of some of these issues. The level of mathematics becomes commensurately more sophisticated.

===Various artifacts of large-insert sequencing===

Biologists have developed methods to filter highly-repetitive, essentially un-sequenceable regions of genomes. These procedures are important for organisms whose genomes consist mostly of such DNA, for example corn. They yield multitudes of small islands of sequenceable DNA products. Wendl and Barbazuk<ref name="wendl05">{{cite journal |author=[[Michael Christopher Wendl|Wendl MC]], Barbazuk WB |year=2005 |title=Extension of Lander–Waterman Theory for sequencing filtered DNA libraries |journal=BMC Bioinformatics |volume=6 |pages=article 245 |doi=10.1186/1471-2105-6-245 |pmid=16216129 |pmc=1280921}}</ref> proposed an extension to Lander–Waterman Theory to account for "gaps" in the target due to filtering and the so-called "edge-effect". The latter is a position-specific sampling bias, for example the terminal base position has only a <math>1 / G</math> chance of being covered, as opposed to <math>L / G</math> for interior positions. For <math>R < 1</math>, classical Lander–Waterman Theory still gives good predictions, but dynamics change for higher redundancies.

Modern sequencing methods usually sequence both ends of a larger fragment, which provides linking information for ''de novo'' assembly and improved probabilities for alignment to reference sequence. Researchers generally believe that longer lengths of data (read lengths) enhance performance for very large DNA targets, an idea consistent with predictions from distribution models.<ref name="wendl06distrib">{{cite journal |author=[[Michael Christopher Wendl|Wendl MC]] |year=2006 |title=Occupancy modeling of coverage distribution for whole genome shotgun DNA sequencing |journal=Bulletin of Mathematical Biology |volume=68 |issue=1|pages=179–196 |doi=10.1007/s11538-005-9021-4 |pmid=16794926 }}</ref> However, Wendl<ref name="wendl06gen">{{cite journal |author=[[Michael Christopher Wendl|Wendl MC]] |year=2006 |title=A general coverage theory for shotgun DNA sequencing |journal=Journal of Computational Biology |volume=13 |issue=6 |pages=1177–1196 |doi=10.1089/cmb.2006.13.1177 |pmid=16901236 }}</ref> showed that smaller fragments provide better coverage on small, linear targets because they reduce the edge effect in linear molecules. These findings have implications for sequencing the products of DNA filtering procedures. Read-pairing and fragment size evidently have negligible influence for large, whole-genome class targets.

===Individual and population sequencing===

Sequencing is emerging as an important tool in medicine, for example in cancer research. Here, the ability to detect [[Loss of heterozygosity|heterozygous mutations]] is important and this can only be done if the sequence of the [[Diploid#Diploid|diploid genome]] is obtained. In the pioneering efforts to sequence individuals, Levy ''et al.''<ref name="levy07">{{cite journal |author=Levy S, ''et al.'' |year=2007 |title=The diploid genome sequence of an individual human |journal=PLoS Biology |volume=5 |issue=10 |pages=article e254 |doi=10.1371/journal.pbio.0050254 |pmid=17803354 |pmc=1964779}}</ref> and Wheeler ''et al.'',<ref name="wheeler08">{{cite journal |author=Wheeler DA, ''et al.'' |year=2008 |title=The complete genome of an individual by massively parallel DNA sequencing |journal=Nature |volume=452 |issue=7189 |pages=872–876 |doi=10.1038/nature06884 |pmid=18421352 |bibcode=2008Natur.452..872W}}</ref> who sequenced [[Craig Venter]] and [[James D. Watson|Jim Watson]], respectively, outlined models for covering both alleles in a genome. Wendl and Wilson<ref name="wendl08">{{cite journal |author=[[Michael Christopher Wendl|Wendl MC]], [[Richard K. Wilson|Wilson RK]] |year=2008 |title=Aspects of coverage in medical DNA sequencing |journal=BMC Bioinformatics |volume=9 |pages=article 239 |doi=10.1186/1471-2105-9-239 |pmid=18485222 |pmc=2430974}}</ref> followed with a more general theory that allowed for an arbitrary number of coverings of each allele and arbitrary [[ploidy]]. These results point to the general conclusion that the amount of data needed for such projects is significantly higher than for traditional haploid projects. Generally, at least 30-fold redundancy, i.e. each nucleotide spanned by an average of 30 sequence reads, is now standard.<ref name="ley2008">{{cite journal |author=[[Timothy Ley|Ley TJ]], ''et al.'' |year=2008 |title=DNA sequencing of a cytogenetically normal acute myeloid leukaemia genome |journal=Nature |volume=456 |issue=7218|pages=66–72 |doi=10.1038/nature07485 |pmid=18987736|bibcode = 2008Natur.456...66L }}</ref>
However, requirements can be even greater, depending upon what kinds of genomic events are to be found. For example, in the so-called "discordant read pairs method", DNA insertions can be inferred if the distance between read pairs is larger than expected. Calculations show that around 50-fold redundancy is needed to avoid [[False positive rate|false-positive errors]] at 1% threshold.<ref name="wendl09a">{{cite journal |author=[[Michael Christopher Wendl|Wendl MC]], [[Richard K. Wilson|Wilson RK]] |year=2009 |title=Statistical aspects of discerning indel-type structural variation via DNA sequence alignment |journal=BMC Genomics |volume=10 |pages=article 359 |pmid=19656394 |doi=10.1186/1471-2164-10-359 |pmc=2748092}}</ref>

The advent of [[DNA_sequencing#Next-generation_methods|next-generation sequencing]] has also made large-scale population sequencing feasible, for example the [[1000 Genomes Project]] to characterize variation in human population groups. While common variation is easily captured, rare variation poses a design challenge: too few samples with significant sequence redundancy risks not having a variant in the sample group, but large samples with light redundancy risk not capturing a variant in the read set that is actually in the sample group. Wendl and Wilson<ref name="wendl09b">{{cite journal |author=[[Michael Christopher Wendl|Wendl MC]], [[Richard K. Wilson|Wilson RK]] |year=2009 |title=The theory of discovering rare variants via DNA sequencing |journal=BMC Genomics |volume=10 |pages=article 485 |pmid=19843339 |doi=10.1186/1471-2164-10-485 |pmc=2778663}}</ref> report a simple set of optimization rules that maximize the probability of discovery for a given set of parameters. For example, for observing a rare allele at least twice (to eliminate the possibility is unique to an individual) a little less than 4-fold redundancy should be used, regardless of the sample size.

===Metagenomic sequencing===

Next-generation instruments are now also enabling the sequencing of whole uncultured metagenomic communities. The sequencing scenario is more complicated here and there are various ways of framing design theories for a given project. For example, Stanhope<ref name="stanhope2010">{{cite journal |author=Stanhope SA |year=2010 |title=Occupancy modeling maximum contig size probabilities and designing metagenomics experiments |journal=PLoS ONE|volume=5 |pages=article e11652 |pmid= 20686599 |doi=10.1371/journal.pone.0011652|bibcode = 2010PLoSO...511652S }}</ref> developed a probabilistic model for the amount of sequence needed to obtain at least one contig of a given size from each novel organism of the community, while Wendl et al. reported analysis for the average contig size or the probability of completely recovering a novel organism for a given rareness within the community.<ref name="wendl2012">{{cite journal |author=[[Michael Christopher Wendl|Wendl MC]] ''et al.''|year=2012 |title=Coverage theories for metagenomic DNA sequencing based on a generalization of Stevens' theorem |journal=Journal of Mathematical Biology |pmid= 22965653 |doi=10.1007/s00285-012-0586-x}}</ref> Conversely, Hooper et al. propose a semi-empirical model based on the [[Gamma distribution]].<ref name="hooper2010">{{cite journal |author=Hooper SD ''et al.''|year=2010 |title=Estimating DNA coverage and abundance in metagenomes using a gamma approximation |journal=Bioinformatics|volume=26 |pages=295–301 |pmid= 20008478 |doi=10.1093/bioinformatics/btp687}}</ref>

==Limitations==

DNA sequencing theories often invoke the assumption that certain random variables in a model are [[Independent and identically-distributed random variables|independent and identically distributed]]. For example, in Lander–Waterman Theory, a sequenced fragment is presumed to have the same probability of covering each region of a genome and all fragments are assumed to be independent of one another. In actuality, sequencing projects are subject to various types of bias, including differences of how well regions can be cloned, sequencing anomalies, biases in the target sequence (which is ''not'' random), and software-dependent errors and biases. In general, theory will agree well with observation up to the point that enough data have been generated to expose latent biases.<ref name="wendl08"/> The kinds of biases related to the underlying target sequence are particularly difficult to model, since the sequence itself may not be known ''a priori''. This presents a type of [[Chicken or the egg|"chicken and egg"]] closure problem.

==See also==

*[[Computational biology]]
*[[Bioinformatics]]
*[[Mathematical biology]]
*[[Sulston score]]

==References==
{{reflist|2}}

[[Category:Bioinformatics]]
[[Category:Mathematical and theoretical biology]]
[[Category:DNA sequencing]]

formulasearchengine - User contributions [en]

Poloidal–toroidal decomposition