formulasearchengine - User contributions [en]

Sfermion

2013-11-04T17:25:34Z

193.137.99.70: /* Squarks */

{{About|Bioinformatics|the disease in horses known by the acronym "PSSM"|Equine polysaccharide storage myopathy}}

[[Image:LexA gram positive bacteria sequence logo.png|200px|thumb|PWMs are often represented graphically as [[sequence logo]]s.]]
A '''position weight matrix (PWM)''', also known as a '''position-specific weight matrix (PSWM)''' or '''position-specific scoring matrix (PSSM)''', is a commonly used representation of [[sequence motif|motifs]] (patterns) in biological sequences.

PWMs are often derived from a set of aligned sequences that are thought to be functionally related and have become an important part of many software tools for computational motif discovery.

==Background==
The position weight matrix was introduced by American geneticist [[Gary Stormo]] and colleagues in 1982<ref name="Stormo1982">{{cite journal|last=Stormo|first=Gary D.|coauthors=Schneider, Thomas D.; Gold, Larry; Ehrenfeucht, Andrzej|title=Use of the ‘Perceptron’ algorithm to distinguish translational initiation sites in ''E. coli''|journal=[[Nucleic Acids Research]]|year=1982|volume=10|issue=9|pages=2997–3011|doi=10.1093/nar/10.9.2997|accessdate=9 November 2013}}</ref> as an alternative to [[consensus sequences]]. Consensus sequences had previously been used to represent patterns in biological sequences, but had difficulties in the prediction of new occurrences of these patterns.<ref name="Stormo1990">{{cite journal|last=Stormo|first=G. D.|title=DNA binding sites: representation and discovery|journal=Bioinformatics|date=1 January 2000|volume=16|issue=1|pages=16–23|doi=10.1093/bioinformatics/16.1.16|accessdate=9 November 2013}}</ref> The first use of PWMs was in the discovery of [[RNA]] sites that function as [[translation (biology)|translation]] initiation sites. The [[perceptron|perceptron algorithm]] was suggested by [[Polish American]] mathematician [[Andrzej Ehrenfeucht]] in order to create a [[matrix (mathematics)|matrix]] of weights which could distinguish true binding sites from other non-functional sites with similar sequences. Training the perceptron on both sets of sites resulted in a matrix and a threshold to distinguish between the two sets.<ref name="Stormo1982" /> Using the matrix to scan new sequences not included in the training set showed that this method was both more sensitive and precise than the best consensus sequence.<ref name="Stormo1990" />

The advantages of PWMs over consensus sequences have made PWMs a popular method for representing patterns in biological sequences and an essential component in modern algorithms for [[sequence motif#De novo computational discovery of motifs|motif discovery]].<ref>{{cite journal|last=Sinha|first=S.|title=On counting position weight matrix matches in a sequence, with application to discriminative motif finding|journal=Bioinformatics|date=27 July 2006|volume=22|issue=14|pages=e454–e463|doi=10.1093/bioinformatics/btl227|accessdate=9 November 2013}}</ref><ref>{{cite journal|last=Xia|first=Xuhua|title=Position Weight Matrix, Gibbs Sampler, and the Associated Significance Tests in Motif Characterization and Prediction|journal=Scientifica|year=2012|volume=2012|pages=1–15|doi=10.6064/2012/917540|accessdate=9 November 2013}}</ref>

==Basic PWM with frequencies==
A PWM has one row for each symbol of the alphabet: 4 rows for [[nucleotide]]s in [[DNA]] sequences or 20 rows for [[amino acid]]s in [[protein]] sequences. It also has one column for each position in the pattern. A basic PWM using relative frequencies is constructed by counting the occurrences of each symbol at each position and then normalising at each position. Formally, given a set ''X'' of ''N'' aligned sequences of length ''l'', the elements of the PWM '''M''' are calculated: 
:<math>M_{k,j}=\frac{1}{N}\sum_{i=1}^N I(X_{i,j}=k),</math> 
where ''i'' <math>\in</math> (1,...,''N''), ''j'' <math>\in</math> (1,...,''l''), ''k'' is the set of symbols in the alphabet and ''I(a=k)'' is an [[indicator function]] where ''I(a=k)'' is 1 if ''a=k'' and 0 otherwise.

For example, given the following DNA sequences: 
:{| class="wikitable"
|-
| <tt>
GAGGTAAAC 
TCCGTAAGT 
CAGGTTGGA 
ACAGTCAGT 
TAGGTCATT 
TAGGTACTG 
ATGGTAACT 
CAGGTATAC 
TGTGTGAGT 
AAGGTAAGT
</tt>
|}
the PWM using relative frequencies is: 
:<math>M = \begin{matrix}
A\\
C\\
G\\
T
\end{matrix}
\begin{bmatrix}
0.3 & 0.6 & 0.1 & 0.0 & 0.0 & 0.6 & 0.7 & 0.2 & 0.1\\
0.2 & 0.2 & 0.1 & 0.0 & 0.0 & 0.2 & 0.1 & 0.1 & 0.2\\
0.1 & 0.1 & 0.7 & 1.0 & 0.0 & 0.1 & 0.1 & 0.5 & 0.1\\
0.4 & 0.1 & 0.1 & 0.0 & 1.0 & 0.1 & 0.1 & 0.2 & 0.6
\end{bmatrix}.
</math><ref name=guigo-pssms>{{cite web|last=Guigo|first=Roderic|title=An Introduction to Position Specific Scoring Matrices|url=http://bioinformatica.upf.edu/T12/MakeProfile.html|work=http://bioinformatica.upf.edu|accessdate=12 November 2013}}</ref>
PWMs assume [[Independence (probability theory)|statistical independence]] between positions in the pattern, as the probabilities for each position are calculated independently of other positions. From the definition above, it follows that the sum of values for a particular position (that is, summing over all symbols) is 1. Each column can therefore be regarded as an independent [[multinomial distribution]]. This makes it easy to calculate the probability of a sequence given a PWM, by multiplying the relevant probabilities at each position. For example, the probability of the sequence ''S'' = <tt>GAGGTAAAC</tt> given the above PWM '''M''' can be calculated: 
:<math>p(S\vert M) = 0.1 \times 0.6 \times 0.7 \times 1.0 \times 1.0 \times 0.6 \times 0.7 \times 0.2 \times 0.2 = 0.0007056.</math> 
[[Pseudocount]]s (or ''[[Laplace estimator]]s'') are often applied to PWMs when a small dataset is used, in order to avoid matrix entries having a value of 0.<ref>{{cite journal|last=Nishida|first=K.|coauthors=Frith, M. C.; Nakai, K.|title=Pseudocounts for transcription factor binding sites|journal=Nucleic Acids Research|date=23 December 2008|volume=37|issue=3|pages=939–944|doi=10.1093/nar/gkn1019|accessdate=Nishida2008}}</ref> This is equivalent to multiplying each column of the PWM by a [[Dirichlet distribution]] and allows the probability to be calculated for new sequences (that is, sequences which were not part of the original dataset): in the example above, without pseudocounts, any sequence which did not have a <tt>G</tt> in the 4th position or a <tt>T</tt> in the 5th position would have a probability of 0, regardless of the other positions.

==Using log likelihoods==
Often the element in PWMs are calculated as log likelihoods. That is, the elements of the PWM are transformed using a background model <math>b</math> so that:
:<math>M_{k,j}=\mathrm{ln}\;(M_{k,j} / b_k).</math>
The simplest background model assumes that each letter appears equally frequently in the dataset. That is, the value of <math>b_k = 1/\vert k \vert</math> for all symbols in the alphabet (0.25 for nucleotides and 0.05 for amino acids). Applying this transformation to the PWM '''M''' from above gives:
:<math>M = \begin{matrix}
A\\
C\\
G\\
T
\end{matrix}
\begin{bmatrix}
0.18 & 0.87 & -0.91 & -\infty & -\infty & 0.87 & 1.02 & -0.22 & -0.91\\
-0.22 & -0.22 & -0.91 & -\infty & -\infty & -0.22 & -0.91 & -0.91 & -0.22\\
-0.91 & -0.91 & 1.02 & 1.38 & -\infty & -0.91 & -0.91 & 0.69 & -0.91\\
0.47 & -0.91 & -0.91 & -\infty & 1.38 & -0.91 & -0.91 & -0.22 & 0.87
\end{bmatrix}.
</math>
The <math>-\infty</math> entries in the matrix make clear the advantage of adding pseudocounts, especially when using small datasets to construct '''M'''. The background model need not have equal values for each symbol: for example, when studying organisms with a high [[GC-content]], the values for <tt>C</tt> and <tt>G</tt> may be increased with a corresponding decrease for the <tt>A</tt> and <tt>T</tt> values.

When the PWM elements are calculated using log likelihoods, the score of a sequence given a particular PWM can be calculated be adding (rather than multiplying) the relevant values at each position in the PWM. The sequence score gives an indication of how different the sequence is from a random sequence. The score is 0 if the sequence has the same probability of being a functional site and of being a random site. The score is greater than 0 if it is more likely to be a functional site than a random site, and less than 0 if it is more likely to be a random site than a functional site.<ref name=guigo-pssms /> The sequence score can also be interpreted in a physical framework as the binding energy for that sequence.

==Information content of a PWM==
The [[information content]] (IC) of a PWM is sometimes of interest, as it says something about how different a given PWM is from a [[uniform distribution (discrete)|uniform distribution]].

The [[self-information]] of observing a particular symbol at a particular position of the motif is:
:<math>-\log(p_{i,j})</math>

The expected (average) self-information of a particular element in the PWM is then:
:<math>-p_{i,j} \cdot \log(p_{i,j})</math>

Finally, the IC of the PWM is then the sum of the expected self-information of every element:
:<math>\textstyle -\sum_{i,j} p_{i,j}\cdot \log(p_{i,j})</math>

Often, it is more useful to calculate the information content with the background letter frequencies of the sequences you are studying rather than assuming equal probabilities of each letter (e.g., the GC-content of DNA of [[thermophilic]] bacteria range from 65.3 to 70.8,<ref name="Aleksandrushkina1978">{{cite journal |author=Aleksandrushkina NI, Egorova LA |title=Nucleotide makeup of the DNA of thermophilic bacteria of the genus Thermus |journal=Mikrobiologiia |volume=47 |issue=2 |pages=250–2 |year=1978 |pmid=661633}}</ref> thus a motif of ATAT would contain much more information than a motif of CCGG). The equation for information content thus becomes
:<math>\textstyle -\sum_{i,j} p_{i,j}\cdot \log(p_{i,j}/p_{b})</math>
where <math>p_{b}</math> is the background frequency for that letter. This corresponds to the [[Kullback-Leibler divergence]] or relative entropy. However, it has been shown that when using PSSM to search genomic sequences (see below) this uniform correction can lead to overestimation of the importance of the different bases in a motif, due to the uneven distribution of n-mers in real genomes, leading to a significantly larger number of false positives.<ref name="Erill2009">{{cite journal |author=Erill I, O'Neill MC |title=A reexamination of information theory-based methods for DNA-binding site identification |journal=BMC Bioinformatics |volume=10 |year=2009 |pmid=19210776 |pages=57 |doi=10.1186/1471-2105-10-57 |pmc=2680408}}</ref>

==Using PWMs==
There are various algorithms to scan for hits of PWMs in sequences. One example is the MATCH algorithm<ref name="Kel2003">{{cite journal |author=Kel AE, ''et al.'' |title=MATCHTM: a tool for searching transcription factor binding sites in DNA sequences |journal=Nucleic Acids Research |volume=31 |pages=3576–3579 |year=2003 |doi=10.1093/nar/gkg585 |pmid=12824369 |issue=13 |pmc=169193}}</ref> which has been implemented in the ModuleMaster.<ref name="Wrzodek2010">{{Cite journal
| last1 = Wrzodek | first1 = Clemens
| last2 = Schröder | first2 = Adrian
| last3 = Dräger | first3 = Andreas
| last4 = Wanke | first4 = Dierk
| last5 = Berendzen | first5 = Kenneth W.
| last6 = Kronfeld | first6 = Marcel
| last7 = Harter | first7 = Klaus
| last8 = Zell | first8 = Andreas
| title = ModuleMaster: A new tool to decipher transcriptional regulatory networks
| journal = Biosystems
| volume = 99
| issue = 1
| pages = 79–81
| publisher = Elsevier
| location = Ireland
| date = 9 October 2009
| year = 2010
| doi = 10.1016/j.biosystems.2009.09.005
| issn = 0303-2647
| pmid = 19819296
}}</ref> More sophisticated algorithms for fast database searching with nucleotide as well as amino acid PWMs/PSSMs are implemented in the possumsearch software and are described by Beckstette, ''et al.'' (2006).<ref name="Beckstette2006">{{cite journal |author=Beckstette, M. |title=Fast index based algorithms and software for matching position specific scoring matrices |journal=BMC Bioinformatics |volume=7 |year=2006 |doi=10.1186/1471-2105-7-389 |pmid=16930469 |pages=389 |pmc=1635428 |display-authors=1 |last2=Homann |first2=Robert |last3=Giegerich |first3=Robert |last4=Kurtz |first4=Stefan}}</ref>

==References==
{{Reflist|2}}

==External links==
* [http://www.biodatamining.org/content/2/1/8 3PFDB] — a database of Best Representative PSSM Profiles (BRPs) of Protein Families generated using a novel data mining approach.
* [http://ugene.unipro.ru/ UGENE] — PSS matrices design, integrated interface to JASPAR, Uniprobe and SITECON databases.

{{Use dmy dates|date=September 2011}}

[[Category:Bioinformatics]]
[[Category:Evaluation methods]]

Nucleon spin structure

2013-01-10T18:01:26Z

193.137.99.89:

In [[mathematics]], the [[geodesic equation]]s are second-order non-linear [[differential equation]]s, and are commonly presented in the form of [[Euler–Lagrange]] equations of motion. However, they can also be presented as a set of coupled first-order equations, in the form of [[Hamilton's equations]]. This latter formulation is developed in this article.

==Overview==
It is frequently said that [[geodesics]] are "straight lines in curved space". By using the Hamilton-Jacobi approach to the [[geodesic equation]], this statement can be given a very intuitive meaning: geodesics describe the motions of particles that are not experiencing any forces. In flat space, it is well known that a particle moving in a straight line will continue to move in a straight line if it experiences no external forces; this is [[Newton's first law]]. The Hamiltonan describing such motion is well known to be <math>H=mv^2/2=p^2/2m</math> with ''p'' being the [[momentum]]. It is the [[conservation of momentum]] that leads to the straight motion of a particle. On a curved surface, exactly the same ideas are at play, except that, in order to measure distances correctly, one must use the [[Metric (mathematics)|metric]]. To measure momenta correctly, one must use the inverse of the metric. The motion of a free particle on a curved surface still has exactly the same form as above, i.e. consisting entirely of a [[kinetic term]]. The resulting motion is still, in a sense, a "straight line", which is why it is sometimes said that geodesics are "straight lines in curved space". This idea is developed in greater detail below.

==Geodesics as an application of the principle of least action==
Given a ([[pseudo-Riemannian manifold|pseudo]]-)[[Riemannian manifold]] ''M'', a [[geodesic]] may be defined as the curve that results from the application of the [[principle of least action]]. A differential equation describing their shape may be derived, using [[variational principle]]s, by minimizing (or finding the extremum) of the [[energy]] of a curve. Given a [[smooth curve]]

:<math>\gamma:I\to M</math>

that maps an interval ''I'' of the [[real number line]] to the manifold ''M'', one writes the energy

:<math>E(\gamma)=\frac{1}{2}\int_I g(\dot\gamma(t),\dot\gamma(t))\,dt,</math>

where <math>\dot\gamma(t)</math> is the [[tangent vector]] to the curve <math>\gamma</math> at point <math>t \in I</math>.
Here, <math>g(\cdot,\cdot)</math> is the [[metric tensor]] on the manifold ''M''.

Using the energy given above as the action, one may choose to solve either the [[Euler–Lagrange equations]], or the Hamilton-Jacobi equations. Both methods give the [[geodesic equation]] as the solution; however, the Hamilton–Jacobi equations provide greater insight into the structure of the manifold, as shown below. In terms of the [[local coordinates]] on ''M'', the (Euler–Lagrange) geodesic equation is

:<math>\frac{d^2x^a}{dt^2} + \Gamma^{a} {}_{bc}\frac{dx^b}{dt}\frac{dx^c}{dt} = 0</math>

Here, the ''x''''a''(''t'') are the coordinates of the curve γ(''t'') and <math>\Gamma^{a} {}_{bc}</math> are the [[Christoffel symbol]]s. Repeated indices imply the use of the [[summation convention]].

==Hamiltonian approach to the geodesic equations==
Geodesics can be understood to be the [[Hamiltonian flow]]s of a special [[Hamiltonian vector field]] defined on the [[cotangent space]] of the manifold. The Hamiltonian is constructed from the metric on the manifold, and is thus a [[quadratic form]] consisting entirely of the [[kinetic term]].

The geodesic equations are second-order differential equations; they can be re-expressed as first-order ordinary differential equations taking the form of the Hamiltonian–Jacobi equations by introducing additional independent variables, as shown below. Start by finding a [[chart (topology)|chart]] that trivializes the [[cotangent bundle]] ''T''∗''M'' (''i.e.'' a ''[[local trivialization]]''):

:<math>T^*M|_{U}\simeq U \times \mathbb{R}^n</math>

where ''U'' is an open [[subset]] of the manifold ''M'', and the tangent space is of rank ''n''. Label the coordinates of the chart as (''x''1, ''x''2, …, ''x''''n'', ''p''1, ''p''2, …, ''p''''n''). Then introduce the [[Hamiltonian vector field|Hamiltonian]] as

:<math>H(x,p)=\frac{1}{2}g^{ab}(x)p_a p_b.</math>

Here, ''g''''ab''(''x'') is the inverse of the [[metric tensor]]: ''g''''ab''(''x'')''g''''bc''(''x'') = <math>\delta^a_c</math>. The behavior of the metric tensor under coordinate transformations implies that ''H'' is [[invariant (mathematics)|invariant]] under a change of variable. The geodesic equations can then be written as

:<math>\dot{x}^a = \frac{\partial H}{\partial p_a} = g^{ab}(x) p_b</math>

and

:<math>\dot{p}_a = - \frac {\partial H}{\partial x^a} =
-\frac{1}{2} \frac {\partial g^{bc}(x)}{\partial x^a} p_b p_c.</math>

The second order geodesic equations are easily obtained by substitution of one into the other. The [[flow (mathematics)|flow]] determined by these equations is called the '''cogeodesic flow'''. The first of the two equations gives the flow on the tangent bundle ''TM'', the '''geodesic flow'''. Thus, the geodesic lines are the projections of integral curves of the geodesic flow onto the manifold ''M''. This is a [[Hamiltonian flow]], and that the Hamiltonian is constant along the geodesics:

:<math>\frac{dH}{dt} = \frac {\partial H}{\partial x^a} \dot{x}^a +
\frac{\partial H}{\partial p_a} \dot{p}_a =
- \dot{p}_a \dot{x}^a + \dot{x}^a \dot{p}_a = 0.</math>

Thus, the geodesic flow splits the cotangent bundle into [[level set]]s of constant energy

:<math>M_E = \{ (x,p) \in T^*M : H(x,p)=E \}</math>

for each energy ''E'' ≥ 0, so that

:<math>T^*M=\bigcup_{E \ge 0} M_E</math>.

==References==
* Terence Tao, ''The Euler-Arnold Equation'', 2010: http://terrytao.wordpress.com/2010/06/07/the-euler-arnold-equation/ ''See the discussion at the beginning''
* Ralph Abraham and Jerrold E. Marsden, ''Foundations of Mechanics'', (1978) Benjamin-Cummings, London ISBN 0-8053-0102-X ''See section 2.7''.
* B.A. Dubrovin, A.T. Fomenko, and S.P. Novikov, ''Modern Geometry- Methods and Applications, Part I'', (1984) Springer-Verlag, Berlin ISBN 0-387-90872-2 ''See chapter 5, in particular section 33''.

[[Category:Symplectic geometry]]
[[Category:Hamiltonian mechanics]]
[[Category:Geodesic (mathematics)]]