Complete and Exact Peptide Sequence Analysis Based on Propositional Logic - Mathematical Approaches to Polymer Sequence Analysis and Related Problems - page 2

its component peptides (via enzymatic digestion and subsequent fractionation with
HPLC or capillary electrophoresis, [ 32 ]), and the original analysis is converted into
a number of peptide analyses which are performed individually. It is worth noting
that this problem has a theoretical structure that is able to represent various other
problems of sequence analysis. At the very basic level, there is a set of possible
components that are individually known a chain formed by some of such compo-
nents, possibly repeated, whose sequence is not known and that cannot be inspected
directly; and the aim is to determine this sequence of components forming the chain.
Nowadays, a widely used and well-established approach to peptide sequence
analysis consists in the use of mass spectrometry [ 19 , 20 , 23 , 28 ]. Such technique
can provide the absolute molecular weight distribution of a number of molecules
in the form of a spectrum : for each molecular weight, the amount of material hav-
ing that molecular weight produces a peak having a certain intensity . The study
of the weight pattern in the spectrum can be used for understanding the structure
of such molecules, especially when using the mass spectrometry/mass spectrome-
try methodology (also known as MS/MS, or tandem mass, [ 29 ]). This procedure
works as follows. After the first mass analysis, some molecules of the protonated
peptide under analysis, called precursor ion , are selected and collided with other
non-reactive elements. This interaction leads to the fragmentation of many of such
molecules, and the collision-generated decomposition products undergo a second
mass analysis. Therefore, such analysis provides the absolute molecular weight of
the full precursor ion, as well as those of the various ionized fragments obtained
from that precursor ion. Non-ionized fragments, on the contrary, do not appear in the
spectrum. Such experiments may be performed using several instrumental config-
urations, mainly triple quadrupole (QQQ), quadrupole time-of-flight (Q-TOF) and
iontrapdevices[ 20 ].
Since the weights of the possible components are known, and rules for deter-
mining the weights of sequences of known composition are available, the MS/MS
information could be used in order to determine the unknown sequence of a peptide.
This is, however, a difficult mathematical problem, as explained in detail in Sect. 1.2 .
Note that the presence of fragments constitutes the only source of information about
the inner structure of the molecule under analysis: in the absence of fragmentation,
the inner structure would be unknown. Several approaches to this problem have
been proposed, as reported in Sect. 1.3 . In particular, a promising approach [ 5 ]is
based on a propositional logic modeling [ 12 , 18 , 31 ] of the problem, as explained
in Sects. 1.4 and 1.5 . It can be shown that all and only the possible outcomes of
a sequence analysis can be obtained by finding all models of a propositional logic
formula. The off-line computation of the so-called weights database, which substan-
tially speeds-up the sequencing operations, is described in Sect. 1.6 . This is obtained
by finding a correspondence between sequences and natural numbers, so that all se-
quences up to a certain molecular weight can be implicitly considered in the above
database, and explicitly computed only when needed. The procedure is illustrated
by considering the case of peptides, but may be adapted to generic polymeric com-
pounds submitted to mass spectrometry. Results on real-world problems, shown in
Sect. 1.7 , demonstrate the effectiveness of this approach.