MASSIS: A Mass Spectrum Simulation System. 2: Procedures and Performance

Abstract

The use of the mass spectral simulation system, MASSIS, is reported and its performance has been evaluated. The search for substructures matching with fragments stored in four pivot databases was realised using the Ullmann algorithm. Special cleavage rules, such as the McLafferty rearrangement, the retro-Diels–Alder reaction, elimination of a neutral small molecule and oxygen migration, are processed through shortest path and depth-first search algorithms. For a search in the database of small fragments, the key step is to determine the tautomeric fragments; then a match can be obtained using a subgraph isomorphism algorithm. A string match is used to determine peak intensity. If the limited environment of an atom is the same as that found in the database of relationships between fragment and intensity, this intensity value is assigned to the query atom. Performance in a set of tests is very important in evaluating the system performance. A comparison of peaks with an intensity greater than 5% (relative) shows that our system has a very high performance figure (> 90%) for routine organic compounds.

Keywords

mass spectral simulation fragment intensity determination comparative study databases Ullmann algorithm software

Get full access to this article

View all access options for this article.

References

Chen

H.F.

Fan

B.T.

Xia

H.R.

Petitjean

Yuan

S.G.

Panaye

Doucet

J.P.

“MASSIS: A Mass Spectra Simulation System 1. Principle and Method,”

Eur. J. Mass Spectrom. 9, 175 (2003).

Garey

M.R.

Johnson

D.S.

, “Computers and Intractability. A Guide to the Theory of NP-Completeness (Appendix A1.4)”, Ed by Klee

, W.H. Freeman and Co., New York, USA (1979).

Corneil

D.G.

Gotlieb

C.C.

, “An Efficient Algorithm for Graph Isomorphism,” J. Assoc. Comput. Machin. 17, 51 (1970).

Ullmann

J.R.

, “An Algorithm for Subgraph Isomorphism,” J. Assoc. Comput. Machin. 23, 31 (1976).

Schmidt

D.C.

Druffel

L.E.

, “A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices,” J. Assoc. Comput. Machin. 23, 433 (1976).

Cordella

L.P.

Foggia

Sansone

Vento

, “Evaluation Performance of the VF Graph Matching Algorithm,” in Proc. of the 10th International Conference on Image Analysis and Processing. IEEE Computer Society Press, pp. 1172–1177 (1999).

Cordella

L.P.

Foggia

Sansone

Tortorella

Vento

, “Graph Matching: A Fast Algorithm and its Evaluation” in Proc. of the 14th International Conference on Pattern Recognition, Brisbane, Australia, August, 16–20, pp. 1582–1584 (1998).

Dijkstra

, “A note on two problems in connection with graphs,” Numerische Mathematik. 1, 269 (1959).

Fan

B.T.

Panaye

Doucet

J.P.

Barbu

, “Ring perception: A new algorithm for finding directly the SSSR from connection table,” J. Chem. Inf. Comput. Sci. 33, 657 (1993).

10.

Fan

B.T.

Barbu

Panaye

Doucet

J.P.

, “Detection of constitutionally equivalent sites from a connection table,” J. Chem. Inf. Comput. Sci. 36, 654 (1996).

11.

Tarjan

, “Depth-First Search and Linear graph Algorithms,” SIAM J. Comput. 1, 146 (1972).

12.

Gasteiger

Hanebeck

Schulz

K.P.

, “Prediction of Mass Spectra from Structural Information,” J. Chem. Inf. Comput. Sci. 32, 264 (1992).