Method and System for Acquiring Molecular Structure of Parent Molecule From Fragment Ions from LC-MS/MS

Abstract

A method of acquiring mass spectrum peak data of fragment ions from mass spectra for fragment ions generated in an LC-MS/MS measuring instrument may include acquiring a molecular structure of the fragment ions and fragment ion graph data by using the acquired data, and deriving a candidate molecular structure of a target substance by assembling fragment ion graphs.

Claims

1. A method of acquiring a molecular structure of a target substance, the method comprising: a fragment ion candidate structure derivation step of deriving candidate structures of fragment ions by inputting mass spectra for fragment ions acquired from an LC-MS/MS analysis of the target substance into a predetermined spectrum-molecular structure database; a fragment ion graphing step of converting the candidate structures of the derived fragment ions into fragment ion graph data; a fragment ion graph assembly step of assembling fragment ion candidate structures by using the fragment ion graph data to acquire candidate molecular structures of the target substance; and a target substance molecular structure determination step of determining a target substance molecular structure from the candidate molecular structures of the target substance in the fragment ion graph assembly step.

2. The method of claim 1, wherein in the fragment ion graphing step, invariable atomic groups included in the fragment ion and linking atoms linked to the invariable atomic groups are expressed as nodes, and information on the invariable atomic groups or linking atoms represented by each of the nodes is expressed as attribute information about each node.

3. The method of claim 2, wherein the fragment ion graph assembly step comprises: a tree node assignment step of assigning fragment ion graphs corresponding to each peak of the mass spectrum to a tree node variable (TN.sub.a.sup.(b)) (b is a depth of a search tree, and a is an order of tree nodes at the depth) in order to perform a tree search operation; a visit node selection step of sequentially selecting and visiting tree nodes of a first depth, excluding tree nodes set as abort nodes; a child tree node creation step of setting a visited tree node (TN.sub.a.sup.(b)) as a parent node and linking all tree nodes (TN.sub.a.sup.(b+1)) corresponding to a following peak as child nodes; an assembly intermediate creation step of creating assembly intermediates in the child nodes by sequentially assembling the fragment ion graphs assigned to the child nodes (TN.sub.a.sup.(b+1)) with assembly intermediate graphs assigned to intermediate node variables of the parent node (TN.sub.a.sup.(b)), assigning an assembly intermediate to an assembly intermediate node variable corresponding to a corresponding child node, and setting the corresponding child node as the abort node when a predetermined assembly intermediate binding condition is not satisfied; and acquiring, as candidate molecular structures of the target substance, final assembly intermediates created by repeating the visit node selection step to the assembly intermediate setting step until there are no more child tree nodes to be created.

4. The method of claim 3, wherein the assembly intermediate creation step comprises: an assembly target fragment ion selection step of selecting the assembly intermediate graph of the parent node and the fragment ion graph of the child node as target fragment ion graph data to be assembled and an input assembly fragment ion graph to be assembled, respectively; a subgraph data extraction step of extracting all subgraphs from the input fragment ion graph data; and a subgraph combination step of sequentially combining all the subgraphs into the target fragment ion graph.

5. The method of claim 4, wherein in the assembly intermediate creation step, at a time of combining the subgraphs, when a molecular weight of the molecule corresponding to the combined graph exceeds the molecular weight of the parent molecule, it is determined that the assembly intermediate binding condition is not satisfied, and the corresponding child node is set as the abort node.

6. The method of claim 4, wherein in the target substance molecular structure determination step, fitness scores of candidate molecular structures of the target substance are calculated and the molecular structure of the target substance from the calculated fitness scores is determined.

7. A system for acquiring a molecular structure of a target substance, the system comprising: an LC-MS/MS measuring unit configured to separate the target substance into fragment ions and generate mass spectra for the fragment ions; a spectrum preprocessing module configured to acquire mass spectrum peak data of fragment ions from the mass spectra of the fragment ions, acquire the molecular structures of fragment ions from a spectrum-molecular structure database using the the mass spectrum peak data, and perform fragment ion graphing on the molecular structures of fragment ions to produce fragment ion graph data; a graph assembly module configured to derive candidate molecular structures of the target substance by receiving the fragment ion graph data and assembling fragment ion graphs; and a spectrum-molecular structure database configured to output molecular structures of the fragment ions by receiving mass spectral peak data on the fragment ions.

8. The system of claim 7, wherein the spectrum preprocessing module is configured to performs fragment ion graphing on a fragment ion molecular structure by expressing invariable atomic groups included in the fragment ion and the linking atoms linked to the invariable atomic groups as nodes and expressing the information about the atomic group or linking atom represented by each node as attribute information about each node.

9. The system of claim 8, wherein the graph assembly module is configured to derives candidate molecular structures of the target substance by assembling fragment ion graphs corresponding to each peak of the fragment ion spectrum to derive candidate molecular structures of the target substance, and when a molecular weight of a molecule corresponding to the combined graph is not smaller than a molecular weight of a precursor ion, it is determined that an assembly intermediate binding condition is not satisfied, and assembly after the corresponding fragment graph is not performed any further.

10. A device for calculating a molecular structure of a target substance, the device comprising: a spectrum preprocessing module configured to receive a fragment ion spectrum of the target substance from an LC-MS/MS measuring instrument and calculate fragment ion-graph data by graphing molecular structures of fragment ions; and a graph assembly module configured to derive candidate molecular structures of the target substance by receiving the fragment ion graph data and assembling fragment ion graphs.

11. The device of claim 10, wherein the spectrum preprocessing module is configured to performs fragment ion graphing on a fragment ion molecular structure by expressing invariable atomic groups included in the fragment ion and the linking atoms linked to the invariable atomic groups as nodes and expressing the information about the atomic group or linking atom represented by each node as attribute information about each node.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0014] The following drawings illustrate aspects of the present disclosure by example, and serve to enable technical aspects of the present disclosure to be further understood together with detailed description of the aspects of the disclosure given above, and therefore the present disclosure should not be interpreted only with matters in such drawings.

[0015] FIG. 1 is a block diagram of a system of acquiring a molecular structure of a parent molecule from fragment ions according to the present disclosure.

[0016] FIG. 2 is an example of mass spectra acquired in the present disclosure.

[0017] FIG. 3 is a flowchart showing a procedure for acquiring the molecular structure of the parent molecule from the fragment ions of the present disclosure.

[0018] FIG. 4 is a diagram for describing graphing of fragment ions according to the present disclosure.

[0019] FIG. 5 is a diagram for describing a process of assembling fragment ion graphs corresponding to mass spectrum peaks according to the present disclosure.

[0020] FIG. 6 is a flowchart showing the process of assembling fragment ion graphs corresponding to mass spectrum peaks according to the present disclosure.

[0021] FIG. 7 is a diagram showing a process of combining fragment ion graphs according to a search tree procedure according to the present disclosure.

[0022] FIG. 8 is a diagram showing an example of assembling a subgraph into an assembly target graph according to the present disclosure.

[0023] FIG. 9 is a flowchart showing a procedure for assembling a subgraph into an assembly target graph according to the present disclosure.

[0024] FIG. 10 is a diagram showing a process of assembling by applying subgraph isomorphism.

[0025] FIG. 11 is an example of pseudocode for implementing a subgraph assembly algorithm according to the present disclosure.

[0026] FIG. 12 is an example of deriving a structure of a parent molecule from graph assembly results according to the present disclosure.

DETAILED DESCRIPTION

[0027] For such a parent molecule structure estimation, it is necessary to estimate the structure of individual fragment ions and then draw the structure of the parent molecule including all of them as partial structures. However, since it is not possible to accurately estimate the structure of a fragment ion using only information provided by the MS/MS spectrum, each fragment ion corresponds to multiple possible candidate structures, and in order to estimate the structure of the parent molecule using the candidate structures, both the structural combinations of respective candidate fragment ions and the number of cases of assembling them have to be explored.

[0028] To this end, the present disclosure allows each fragment structure to overlap each other and assembles it, but estimates the structure of the parent molecule through an algorithm that extracts the number of all cases in which a molecule from which all pieces are assembled is identical to the elemental composition of the parent molecule.

[0029] Hereinafter, referring to FIGS. 1 to 12, a method and a system of acquiring a molecular structure of a target substance (parent molecule) from fragment ions generated during liquid chromatography-tandem mass spectrometry (LC-MS/MS LC-MS/MS) analysis of the target substance, according to the present disclosure, will be described.

1. Parent Molecule Molecular Structure Acquisition System

[0030] As shown in FIG. 1, a system of the present disclosure includes an LC-MS/MS measuring unit 100, a spectrum preprocessing module 200, a graph assembly module 300, and a spectrum-molecular structure database (DB) 400.

[0031] The LC-MS/MS measuring unit 100 includes a typical LC-MS/MS measuring instrument (liquid chromatography-tandem mass spectrometry (LC-MS/MS)). The device separates a target substance (parent molecule) into fragment ions and generates mass spectra for the fragment ions.

[0032] FIG. 2 shows an example of mass spectra generated from fragment ions. The mass spectra for fragment ions may be acquired as a graph constituted by a mass axis (molecular weight) and an ionic intensity axis that represent the mass of each fragment ion in mass-charge ratio (m/z), and when a specific mass (m/z) in the mass spectrum of a fragment ion is found in the graph, the molecular weight of the fragment ion may be calculated. In this case, since the quantity of charge of the fragment ion is usually 1, the mass and molecular weight of the fragment ion may be said to be almost the same, and therefore, the m/z value of the fragment ion may be used as the molecular weight. For example, when the m/z value of the fragment ion is 200, the molecular weight of the fragment ion may be said to be 200 Dalton (g/mol). Among the fragment ion spectrum information, molecular weight information is used to acquire the molecular structure of fragment ions from the spectrum-molecular structure DB 400.

[0033] The ionic intensity value is related to the amount of fragment ions generated. A high ionic intensity value means that the number of times pieces are cut is high, and usually, since fragment ions positioned in the center of a compound molecule have high stability and are less likely to be cut into fragment ions, when a final parent molecule candidate structure is derived, fragment ions with high ionic intensity values are positioned in the center, and thus a structure having to break multiple bonds is highly likely to be a candidate structure that does not fit the actual parent molecule structure.

[0034] The spectrum preprocessing module 200 acquires mass spectrum peak data (molecular weight, ionic intensity value of each fragment ion) of each of fragment ions constituting the target substance from the LC-MS/MS measuring unit 100, acquires the molecular structure of fragment ions by inputting the data into the spectrum-molecular structure DB, and reconstructs the molecular structures of the acquired fragment ions into fragment ion graph data. The spectrum-molecular structure DB is a database containing known mass spectrum data and corresponding molecular structure data on molecules and known spectrum-molecular structure DBs include NIST Chemistry WebBook, NIST Mass Spectral Library, METLIN, PubChem, ChemSpider, and the like, but the scope of the present disclosure is not limited to the use of a specific database, and as a database loaded with its own data, any database containing mass spectrum data on a given molecule and corresponding molecular structure data may be applied to the system of the present disclosure.

[0035] The spectrum preprocessing module 200 receives molecular structure data on the fragment ions corresponding to the mass spectrum data on the fragment ions input from the spectrum-molecular structure DB and reconstructs the received data into graph data.

[0036] In the present disclosure, graph refers to an expression of a certain molecular structure in the form of a graph, and graph data refers to a conversion of the graph into numerical data that is able to be processed by computer operations. Graph data may include nodes that make up the graph, edges that link nodes, node properties, and edge property data, and may be expressed as matrix data such as an adjacency matrix or the like that expresses them, but is limited to a specific data format.

[0037] The fragment ion graph, which the molecular structures of fragment ions are reconstructed as graph data according to the present disclosure, expresses each invariant atom group as one node, expresses atoms that are not invariant atom groups as other nodes linked to the invariant atom group node, and has an edge linking each node (node: this is a node expressing the molecular structure and is different from the tree node, parent node, and child node described below). The fragment ion graph data may be graph data including variables expressing each node of the fragment ion graph and node attribute data, and edge variables linking the nodes and edge attribute data.

[0038] The graph assembly module 300 may receive fragment ion graph data obtained by graphing the fragment ions, assemble fragment ion graphs according to a fragment ion assembly method of the present disclosure, which will be described below, and calculate assembly intermediate graph data, which is fragment ion combining molecular graph data, and further output the assembly intermediate graph data as a fragment ion binding molecular structure, that is, a candidate structure for the estimated parent molecule. The graph assembly module 300 may include a parent molecular structure determination module (not shown) to determine the final parent molecular structure from the candidate structures through a likelihood evaluation operation described below.

[0039] In the present disclosure, the spectrum preprocessing module 200 and the graph assembly module 300 may each be a separate data operation module, or may be a single computing device or computer device. In this case, each calculation module, calculation device, or computer device may be configured to include a storage device and a calculation device that store, read, and calculate a computer-implemented algorithm for performing graphing of the fragment ions and a graph combining method, which will be described below.

2. Method of Acquiring Molecular Structure of Parent Molecule

[0040] Referring to FIG. 3, the method of acquiring the molecular structure of the parent molecule according to the present disclosure will be generally described.

(1) Fragment Ion Candidate Structure Acquisition Step (S100)

[0041] First, by performing the following procedures, candidate structures of fragment ions are acquired.

[0042] In order to derive the molecular structure of a given target substance (target compound, parent molecule) having the molecular structure that is unknown, LC-MS/MS analysis is first performed on a sample containing the target substance.

[0043] In LC-MS/MS analysis, the target substance in the sample, that is, the target compound in the sample, is separated through liquid chromatography (LC), the target compound is input into the MS/MS equipment, fragment ions are generated, and a mass spectrum (MS/MS spectrum) for the generated fragment ions is generated, where the present disclosure begins a process of estimating the molecular structure of the parent molecule by acquiring mass spectrum data on the fragment ions generated at this time.

[0044] Next, the mass spectra for the acquired fragment ions are input into the spectrum-molecular structure DB 400 to derive a candidate structure of a fragment ion matching a corresponding spectrum. As shown in the example in FIG. 4, since it is difficult to know in advance which fragment ion will correspond to each peak in the mass spectrum, a list of all fragment ions of the same elemental composition is retrieved and assembly is performed for each of them. A number of fragment ions that make up the list of the fragment ions corresponding to each peak in the mass spectrum are referred to as candidate fragments.

(2) Fragment Ion Graphing Step (S200)

[0045] Next, this is a step of acquiring fragment ion graph data by performing fragment ion graphing of the molecular structures of the candidate fragments acquired from the database and converting the fragment ion graphs into data that is able to be processed by computer operations. Converting the fragment ion graph into the fragment ion graph data that is able to be processed by computer operations is to express the fragment ion graph as a graph adjacency matrix, node attribute matrix, and edge attribute matrix including graph nodes and their attribute information, edges, and edge attribute information as described below, which is well known to those skilled in the art.

[0046] In the present disclosure, fragment ion candidate structures are referred to as candidate fragments, and when representing them as graph data, the invariant atomic group contained in the fragment ion, which is always detected in a combined form on the MS/MS spectrum, is expressed as a single node. Atoms that do not belong to the invariant atomic group are expressed as one node. The information about each invariant atomic group and atom is expressed as attribute information about each node.

[0047] For example, as shown in FIG. 4, benzene is an invariant atomic group that is always detected in its complete form and is treated as one node. However, for carbazole, the central pentagonal structure is sometimes decomposed and detected as a bond of benzene and nitrogen atoms, and thus, the carbazole is not treated as an invariant atomic group, but is expressed as a linkage between a benzene node and a nitrogen node, which are invariant atomic groups.

(3) Fragment Ion Assembly Step (S300)

[0048] Next, fragment ion graphs representing candidate structures of fragment ions are assembled to derive candidate structures of the parent molecule.

[0049] However, it is difficult to know in advance which fragment ion will correspond to a peak of the MS/MS spectrum. Therefore, all lists of the fragment ions with elemental compositions corresponding to each peak of the spectrum are retrieved from the spectrum-molecular structure DB 400, and then assembly is performed for each of them. When there are N peaks {p.sub.1, p.sub.2, . . . , p.sub.N} in the mass spectrum, and there are n.sub.i candidate fragment ions that are able to correspond to each peak P.sub.i, the total number of fragment ion combinations that have to be assembled becomes

[00001]${.Math.}_{i=1}^N{n}_i,$

and the calculation takes a very long time.

[0050] Therefore, in the present disclosure, when any two combinations share most of the fragment ion combinations, it is determined that it would be inefficient to assemble each of them from scratch, and a method of minimizing duplicate path visits by conducting an assembly process in the form of a search tree is applied. During the tree search process, pruning and excluding nodes that may no longer be assembled eliminates the need to visit all nodes branching from that node, thereby drastically shortening the time. This will be described with reference to FIG. 5.

[0051] In the present disclosure, N peaks are listed in order of size, and then a search tree for which a search node is an action of selecting one of the fragment ion candidates is created. A node with depth i corresponds to an action of selecting which fragment ion to assemble at an i-th peak. Applying the principle, the present disclosure performs tree search in the following order. In this way, the tree search process assigns the fragment ion graphs corresponding to each peak to the corresponding tree node variables and performs a tree search operation.

[0052] FIG. 5 is a view illustrating the process of selecting bound fragment ions when there are five peaks in the mass spectrum and the number of candidate fragment ions corresponding to peaks is three, four, two, one, and one, respectively. With reference to FIGS. 5 and 6, a specific procedure of tree search operation will be described.

[0053] In the example of FIG. 5, three tree nodes are assigned to peak.sub.1, and four tree nodes are assigned to peak.sub.2. Each tree node variable corresponds to fragment ion graph data of each fragment ion. In the example of FIG. 5, the number of possible combinations of fragment graphs is 3*4*2*1*1=24 cases, and according to the combining method of the present disclosure, the number of possible combinations is reduced, saving computational resources.

(a) Tree Node Assignment Step (S31)

[0054] In order to perform a tree search operation, fragment ion graphs corresponding to each peak of the mass spectrum are assigned to each tree node variable of the search tree. A root node of the search tree is set to be with an empty graph. Corresponding fragment ion graphs are assigned to each node of each peak, and each fragment ion graph may be expressed as g_frag.sub.i.sup.(k) (k represents a peak number and i represents a fragment graph number of the peak).

[0055] Fragment ion graphs corresponding to each peak are assigned to tree nodes for each depth of the search tree. For example, a starting node of the search tree is assigned to a root node with an empty graph, and the fragment ion graphs corresponding to peak_b are assigned to tree nodes at depth b.

[0056] As shown in FIG. 7, in the search tree, the starting node may be TN.sub.root, and other tree nodes may be expressed as TN.sub.a.sup.(b) variables (b is the depth of the search tree, and a is the order of tree nodes at that depth).

(b) Visit Node Selection Step (S32)

[0057] This is a step of sequentially selecting and visiting the tree nodes to be visited among the tree nodes. In practice, the step may be implemented with a computer algorithm in which a predetermined tree node selection pointer sequentially points to each of the tree nodes.

[0058] Fragment graph assembly procedures to be described below are performed by selecting the first tree node of the first peak, graph assembly procedures to be described below are performed by sequentially selecting all corresponding tree nodes of one peak, and then tree nodes of the next peak are selected. Meanwhile, the selection order of tree nodes is not limited thereto, and it is sufficient to go through the process of selecting all tree nodes of all peaks regardless of their order.

[0059] The selection of tree nodes is performed in a procedure to be described below, excluding tree nodes marked as abort according to a predetermined condition. The indication of abort may be displayed as abort for the tree node by changing the value of a certain flag in the tree node variables, and the indication of abort does not mean stopping the procedure, but rather means that the graph assembly is not performed for the fragment graph corresponding to the tree node.

[0060] The visit node selection step may begin with visiting the first parent node among the top parent nodes. In the subsequent iteration step, when the visit node is marked as abort, the next node is visited without performing a subsequent procedure.

(c) Child Node Creation Step (S33)

[0061] For the visited tree node, a child node corresponding to each of fragment ion graphs of a peak following the peak to which the corresponding tree node corresponds is created. This is a step of generating the number of cases in which each fragment ion candidate that is able to correspond to the following peak is assembled in the graph assembled so far.

(d) Assembly Intermediate Graph Generation Step (S34)

[0062] This is the step of generating an assembly intermediate graph at each child node by assembling the corresponding fragment ion graph (child node graph) with the assembly intermediate graph of the parent node at each child node. Each tree node may be assigned a corresponding assembly intermediate node variable, and as the child node, the assembly intermediate graph of its parent node and the assembled assembly intermediate graph may be stored in correspondence.

[0063] In this case, in the assembly intermediate graph generation step (S34), at each child node, the assembly intermediate graph stored in the assembly intermediate node variable of the parent node and child node graph are assembled, and graph data as the assembly result is stored in the assembly intermediate node variable of the child node to be used for assembly with the child node graph of the next depth. After generating the assembly intermediate graphs for all child nodes, when a corresponding peak is not the last peak, each child node is visited and the process returns to the visit node selection step (S32).

[0064] Meanwhile, among the child nodes that satisfy a predetermined condition to be described below, child nodes that are not able to create any assembly intermediate with the parent node are added to the list of abort nodes.

(e) Parent Molecule Candidate Structure Derivation Step (S35)

[0065] This is a step of acquiring a final updated assembly intermediate graph by repeating steps S32 to S34 until a node of depth N corresponding to the last peak of the peak list is created, and acquiring a candidate molecular structure of the parent molecule (target substance) therefrom.

[0066] For the example of FIG. 5, the above-described procedures S31 to S35 will be described with reference to FIG. 7 as an example. In the example of FIG. 5, since there are five peaks from p.sub.1 to p.sub.5 and the fragment ions corresponding to each peak are one, one, two, four, and three, respectively, the number of graph combinations to be considered in the normal method is 1*1*2*4*3=24 types. However, according to the abort node pruning method applied in the present disclosure, the number of combinations is reduced, thereby increasing computational efficiency.

[0067] The assembly order of each peak may be arbitrarily selected, and in FIG. 7, a case of assembly in the order p.sub.5.fwdarw.p.sub.4.fwdarw.p.sub.3.fwdarw.p.sub.2.fwdarw.p.sub.1 will be described. TN.sub.a.sup.b is assigned to each tree node variable in the search tree, where a represents a node serial number and b represents a tree depth. For example, TN.sub.2.sup.(1) refers to a second node at Depth 1, and TN.sub.12.sup.(2) refers to a 12-th node at Depth 2. Likewise, the assembly intermediate graph corresponding to each tree node TN.sub.a.sup.(b) is expressed as G.sub.a.sup.(b).

[0068] (a) in FIG. 7 shows an initial start of a tree search, that is, a step in which a root node is selected as a visit node (S32).

[0069] In the next step, at Depth 1, child nodes to which fragment ion graphs frag.sub.1 to 3.sup.(5) corresponding to peaks are assigned are generated (S33) as child nodes of the visit node. As for the child nodes, in the example of FIG. 5, since three fragment ion graphs correspond to peak.sub.5, three child nodes are created. In the next step, each child node is assembled with the root node to generate an assembly intermediate graph (S34). Since the root node has no corresponding peak or fragment ion, at Depth 1, the assembly intermediate graph generated from the three child nodes is the same as each fragment ion graph at peaks. That is, at Depth 1, the tree nodes TN.sub.1 to 3.sup.(1) are created as child nodes of the root node, and the fragment ion graphs frag.sub.1 to 3.sup.(5) are assigned assembly intermediates G.sub.1 to 3.sup.(1) corresponding to the tree nodes TN.sub.1 to 3.sup.(1), respectively (a fragment ion graph is expressed as frag.sub.a.sup.(b), where b is a peak number to which the fragment ion corresponds, and a is the fragment ion graph number of the corresponding peak.)

[0070] Since the peak in the procedure shown in (a) in FIG. 7 is not the final peak, as shown in (b) in FIG. 7, by returning to the visit node selection step, the tree nodes corresponding to the generated peaks are selected as visit nodes (S32), and for each tree node of peaks, child nodes to which the fragment ion graphs corresponding to peak.sub.4 are assigned are created (S33). Since four fragment ions correspond to peak.sub.4, four child nodes are assigned to each of the nodes corresponding to peaks. Now, at each of the child nodes (a total of 12), the assembly intermediate graph of the parent node and the fragment ion graph corresponding to the child node are combined to generate an assembly intermediate graph corresponding to the child node in this step (S34). An assembly intermediate G.sub.1.sup.(2) corresponding to TN.sub.1.sup.(2) is frag.sub.1.sup.(5)+frag.sub.1.sup.(4), and an assembly intermediate G.sub.2.sup.(2) corresponding to TN.sub.2.sup.(2) is frag.sub.1.sup.(5)+frag.sub.2.sup.(4).

[0071] When the molecular weight in the assembly intermediate graph resulting from such a combination becomes greater than the molecular weight of the parent molecule before the target substance is input into a mass spectrometer, the combination does not seem to satisfy the binding condition, and thus the node is set as an abort node. In FIG. 7, the case where since the assembly intermediate graphs with the parent node assembly intermediates assembled in TN.sub.3.sup.(2), TN.sub.4.sup.(2), TN.sub.6.sup.(2), TN.sub.8.sup.(2), TN.sub.9.sup.(2), and TN.sub.11.sup.(2) do not satisfy the predetermined combination to be described below, TN.sub.3.sup.(2), TN.sub.4.sup.(2), TN.sub.6.sup.(2), TN.sub.8.sup.(2), TN.sub.9.sup.(2), and TN.sub.11.sup.(2) are set as abort nodes is shown.

[0072] Since the last peak has not yet been reached, by returning to the visit node selection step (S32), as shown in (c) in FIG. 7, for each tree node of peak.sub.2, the tree nodes of peak.sub.3 are created as child nodes (S34), and an assembly intermediate graph corresponding to each tree node of peak.sub.2 is generated. In this case, even when TN.sub.3.sup.(2), TN.sub.4.sup.(2), TN.sub.6.sup.(2), TN.sub.8.sup.(2), TN.sub.9.sup.(2), and TN.sub.11.sup.(2), which have been previously set as abort nodes, are visited, the child node creation and assembly intermediate creation steps are not performed, so that the amount of computation may be reduced. In this way, for all nodes TN.sub.a.sup.(3) at Depth 3, the visit, child node creation, and assembly intermediate creation processes are performed, and then the visit node selection step is performed again at the next depth. This process is repeated until the last peak is reached.

(f) Parent Molecular Structure Determination Step (S36)

[0073] Next, an optimal candidate molecular structure is selected from among the candidate molecular structures that are the final assembly intermediates assembled while the last peak is reached, and is determined as a final parent molecular structure. The final parent molecular structure may be determined through likelihood evaluation of candidate molecular structures.

[0074] When it is assumed that a derived candidate molecular structure is and the fragment ion mass spectrum applied to derive the candidate molecular structure is X=x.sub.0, x.sub.1, . . . , x.sub.i (x.sub.k is a peak group consisting of consecutive deprotonation peaks, that is, a set of consecutive peaks with a difference of one hydrogen), in this case, the probability of the occurrence of the peak group X by the candidate molecular structure may be expressed as the product of the probabilities of occurrences of individual peaks in the set X occurs by the candidate molecular structure , as shown in Equation 1 below, and the likelihood evaluation is to find a structure that maximizes a likelihood expressed by Equation 1.

[00002]$\begin{array}{cc}p\left(.Math.X\right)~{.Math.}_{k}p\left(.Math.x_k\right)& \left(\mathrm{Equation}1\right)\end{array}$

[0075] When, it is assumed that, for each peak

[00003]$x_i^{\left(k\right)}=\left(m_i^{\left(k\right)},r_i^{\left(k\right)}\right)$

with m/z

[00004]$m_i^{\left(k\right)}$

and normalized intensity

[00005]$r_i^{\left(k\right)}$

in the peak group x.sub.k, when a corresponding structure among the partial structures of is

[00006]$S_{m_i^{\left(k\right)}},$

the likelihood for the peak group may be expressed as Equation 2 below again.

[00007]$\begin{array}{cc}p\left(.Math.x_k\right)={.Math.}_{i}p\left(S_{m_i^{\left(k\right)}}.Math.r_i^{\left(k\right)}\right)& \left(\mathrm{Equation}2\right)\end{array}$

(m.sub.i.sup.(k)) and r.sub.i.sup.(k) is the m/z and the normalized intensity of the peak group x.sub.k, respectively)

[0076] Here, in order to generate

[00008]$S_{m_i^{\left(k\right)}}$

from fragmentation has to be performed a.sub.i.sup.(k) times and deprotonation has to be performed b.sub.i.sup.(k) times, and assuming that each probability is expressed as constants independent of the structure, p.sub.J (probability of breaking a certain binding) and p.sub.J (probability of one additional hydrogen being removed from a substructure), maximizing the likelihood

[00009]$p\left(S_{m_i^{\left(k\right)}}.Math.s_i^{\left(k\right)}\right)$

for an individual peak is equivalent to minimizing the crossentropy in Equation 3 below.

[00010]$\begin{array}{cc}\mathrm{crossentropy}=-r_i^{\left(k\right)}\log \left(p_f^{a_i^{\left(k\right)}}{p}_f^{b_i^{\left(k\right)}}\right)& \left(\mathrm{Equation}3\right)\end{array}$

(log p.sub.J and log p.sub.a are each a hyperparameter and are values selected from the above-mentioned spectrum-molecular structure database, a is the number of bindings that have to be broken to generate a fragment ion graph S in the final result graph , and b is the number of hydrogens additionally removed from the fragment ion)

[0077] Combining Equations 1 to 3, a fitness score of each candidate structure may be defined as Equation 4 below.

[00011]$\begin{array}{cc}\mathrm{score}\left(,X\right)=-\underset{k}{.Math.}\underset{i}{.Math.}{r}_i^{\left(k\right)}\left(a_i^{\left(k\right)}\log p_f+b_i^{\left(k\right)}\log p_d\right)& \left(\mathrm{Equation}4\right)\end{array}$

(log p.sub.J and log p.sub.d are each hyperparameter and are values selected from the above-mentioned spectrum-molecular structure database, a is the number of bindings that have to be broken to generate the fragment ion graph S in the final result graph , and b is the number of hydrogens additionally removed from the fragment ion)

[0078] In this way, the fitness for each candidate structure is calculated through calculation according to the equations, and according to the calculated fitness, the final candidate structure of the target substance is calculated from the final assembly intermediate graph obtained by assembling the fragment ion graphs.

(4) Detailed Description of the Assembly Intermediate Graph Generation Step (S34)

[0079] In the assembly intermediate graph generation step, the algorithm for generating the assembly intermediate graph will be described in more detail with reference to FIGS. 8 to 11.

[0080] Since each peak in the MS/MS spectrum represents the fragment ion obtained by decomposing the parent molecule using different methods, there is overlap between the molecular structures of the detected candidate fragments. Therefore, when fragment ion graphs are combined, overlap has to be allowed and the number of all possible cases of assembling the given graphs according to the elemental composition of the parent molecule has to be extracted and assembled.

[0081] FIG. 8 shows an example in which, when assembling is performed in the order of {circle around (1)}.fwdarw.{circle around (2)}.fwdarw.{circle around (3)}.fwdarw.{circle around (4)}, only two cases are picked up in each step, schematically illustrating a form in which assembly is possible by allowing overlap.

[0082] FIG. 9 shows a specific algorithm for the assembly intermediate generation procedure (S34).

(a) Assembly Target Graph Selection Step (G10)

[0083] Two graphs to be assembled from the fragment ion graphs expressing candidate structures of the fragment ion are selected. Selection of the graph to be assembled is repeated until all fragment ion graphs are selected as assembly targets and assembly is completed.

[0084] This step is a step of selecting the assembly intermediate graph of the parent node and the fragment ion graph of the child node as target fragment ion graph data to be assembled and an input assembly fragment ion graph to be assembled, respectively, after creating the child tree nodes at the visit node in the previous S33.

(b) Subgraph Extraction Step (G20)

[0085] A step of selecting and assembling the first fragment ion graph to be assembled is referred to as step t, and a step of selecting and assembling the second graph to be assembled is referred to as step t+1.

[0086] Among the graphs to be assembled, the fragment ion graph to be assembled is referred as a target graph (current graph), and the target graph at step t is called g.sub.c.sup.(t) (current graph at step t). The graph to be assembled is referred to as an input graph (incoming graph) and is expressed as g.sub.i (incoming graph). A set of all resulting graphs where the two graphs are assembled is referred to as G.sup.(t+1).

[0087] FIG. 10 shows a case where G1 is selected as the target graph g.sub.c and G.sub.2 is selected as the input graph g.sub.i. G1 includes node n.sub.i (i=0 to 5), and G2 includes node n.sub.k (k=0 to 3).

[0088] This is a step of extracting all subgraphs Si of the graph to be assembled, that is, g.sub.i of the input graph (incoming graph). FIG. 10 shows that three subgraphs are extracted, with nodes (0, 1), (0, 1, 2), and (2, 3) of G2 as nodes. The algorithm for extracting a subgraph from a graph is a known algorithm.

(c) Subgraph Assembly Step (G30)

[0089] Next, a subgraph assembly step is performed in which all subgraphs Si of the input graph g.sup.i are sequentially assembled into g.sub.c.

{circle around (1)} Partial Graph Initialization Step (G31)

[0090] The assembly of the subgraph begins by setting the target graph (current graph) to g.sub.c.sup.(t), an incoming graph to be assembled to g.sub.i, and a resulting graph set G.sup.(t+1) to an empty set.

{circle around (2)} Node Mapping Step (G32)

[0091] Next, for each subgraph Si (g.sub.i) of the incoming graph g.sub.i, isomorphic graph identification (subgraph isomorphism) and node mapping with the target graph g.sub.c.sup.(t) are performed.

{circle around (3)} Node/Edge Binding Step (G33)

[0092] When it is assumed that mapping of all nodes M, the subgraph isomorphic graph identification of Si and g.sub.c.sup.(t) is M.sub.k={(v.sub.i,v.sub.c)|v.sub.iS.sub.i,v.sub.cg.sub.c.sup.(t)}, and a complement graph of subgraph Si is Si.sup.c, for each and every node mapping M.sub.k(M), {circle around (a)} a procedure of substituting g.sub.c.sup.(t) into g.sub.c.sup.(t+1) and adding all nodes and edges of Si.sup.c to g.sub.c.sup.(t+1), {circle around (b)} a procedure of adding all edges of g.sub.i that do not belong to Si and Si.sup.c to g.sub.c.sup.(t+1) and {circle around (c)} a procedure of adding g.sub.c.sup.(t+1) to G.sup.(t+1) are performed. In this case, the sum of the molecular weight of g.sub.c.sup.(t) and the molecular weight of Si.sub.c has to be equal to or smaller than the molecular weight of the parent molecule. When the sum of the molecular weight of g.sub.c.sup.(t) and the molecular weight of Si.sup.c exceeds the molecular weight of the parent molecule, a determination of inability to bind is made.

[0093] The above procedures {circle around (2)} and {circle around (3)} are performed for all subgraphs Si of g.sub.i.

[0094] An example of pseudocode that performs the above-described procedures is shown in FIG. 11, and an example of a resulting graph of binding through the procedures is shown in FIG. 12.

[0095] Names of respective symbols in drawings used in the present disclosure are as follows. [0096] 100 LC-MS/MS MEASURING UNIT [0097] 200 SPECTRUM PREPROCESSING MODULE [0098] 300 GRAPH ASSEMBLY MODULE [0099] 400 SPECTRUM-MOLECULAR STRUCTURE DB