Bioinformatics, 35, 2019, i164–i172
doi: 10.1093/bioinformatics/btz319
ISMB/ECCB 2019

Dai Hai Nguyen1,*, Canh Hao Nguyen1 and Hiroshi Mamitsuka1,2
1

Bioinformatics Center, Institute for Chemical Research, Kyoto University, Uji 611-0011, Japan and 2Department ofComputer Science, Aalto University, Espoo, Finland*To whom correspondence should be addressed.

Abstract
Motivation: Metabolite identification is an important task in metabolomics to enhance the knowledge of biological systems. There have been a number of machine learning-based methods proposed for this task, which predict a chemical structure of a given spectrum through an intermediate(chemical structure) representation called molecular fingerprints. They usually have two steps:(i) predicting fingerprints from spectra; (ii) searching chemical compounds (in database) corresponding to the predicted fingerprints. Fingerprints are feature vectors, which are usually verylarge to cover all possible substructures and chemical properties, and therefore heavily redundant,
in the sense of having many molecular (sub)structures irrelevant to the task, causing limited predictive performance and slow prediction.
Results: We propose ADAPTIVE, which has two parts: learning two mappings (i) from structures tomolecular vectors and (ii) from spectra to molecular vectors. The first part learns molecular vectors
for metabolites from given data, to be consistent with both spectra and chemical structures ofmetabolites. In more detail, molecular vectors are generated by a model, being parameterized by amessage passing neural network, and parameters are estimated by maximizing the correlation between molecular vectors and the corresponding spectra in terms of Hilbert-Schmidt Independence
Criterion. Molecular vectors generated by this model are compact and importantly adaptive (specific) to both given data and task of metabolite identification. The second part uses input output kernel
regression (IOKR), the current cutting-edge method of metabolite identification. We empiricallyconfirmed the effectiveness of ADAPTIVE by using a benchmark data, where ADAPTIVE outperformed the original IOKR in both predictive performance and computational efficiency.
Availability and implementation: The code will be accessed through http://www.bic.kyoto-u.ac.jp/
pathway/tools/ADAPTIVE after the acceptance of this article.
Contact: hai@kuicr.kyoto-u.ac.jp

1 Introduction
Metabolites are small molecules, having many important functions inliving cells such as energy transport, signaling, building blocks of cells
and so on (Wishart, 2007). Identifying their biochemical characteristics or so-called metabolite identification is an essential task in metabolomics to increase the knowledge of biological systems. Yet, it is stilla challenging task due to the size or coverage of spectra libraries.
Mass spectrometry (MS) is one of the most common techniques
in analytical chemistry for dealing with metabolite identification (deHoffmann and Stroobant, 2007). In more detail, a chemical

C The Author(s) 2019. Published by Oxford University Press.
V

compound is decomposed into fragments, of which mass-to-charge
ratios (m/z) are continuously measured to obtain a mass spectrum.
One MS spectrum can be represented by a list of peaks, each ofwhich corresponds to a fragment captured by MS. Figure 1 shows areal example of a MS spectrum. In practice, tandem MS (also known
as MS/MS or MS2) is widely used, in which precursor ions of specific m/z values from MS spectra are selected and further fragmented
to produce other groups of product ions [see, e.g. Vaniya and Fiehn(2015) for more details]. The MS/MS spectra provide structural information about the measured compound, which makes MS/MS
more useful for tackling metabolite identification.

i164

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/4.0/),
which permits non-commercial re-use, distribution, and reproduction in any medium, provided the original work is properly cited. For commercial re-use, please contact
journals.permissions@oup.com

Downloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019

ADAPTIVE: leArning DAta-dePendenT, concIse
molecular VEctors for fast, accurate metabolite
identification from tandem mass spectra

Learning adaptive molecular vectors for metabolite identification

A number of computational methods have been proposed for
identifying unknown metabolites from MS/MS spectra data. In general, they are classified into three main categories: (i) spectral library
search; (ii) in silico fragmentation; and (iii) machine learning(Nguyen et al., 2018a). Recent advances in metabolite identification
have been led by the machine learning category (e.g. Brouard et al.,2016; Dührkop et al., 2015; Nguyen et al., 2018b). This category
can be further divided into two key groups: supervised learning for
substructure prediction and unsupervised learning for substructure
annotation. While the former is to find a mapping from inputs (e.g.
spectra) to outputs (e.g. fingerprints), the latter extracts underlying
substructures of metabolites. Our research focuses on supervised
learning, where the common scheme is to learn a mapping fromspectra to structures.
The prediction can be divided into two steps: (i) fingerprint prediction: predicting fingerprints of a given test spectrum with supervised learning; (ii) candidate retrieval: retrieving chemical compound(from database) which is closest to the predicted fingerprints (Nguyen
et al., 2018b).
Kernel methods have been shown to be effective for fingerprint
prediction, such as methods include FingerID (Heinonen et al.,2012), CSI:FingerID (Dührkop et al., 2015) and input output kernel
regression (IOKR, Brouard et al., 2016). In particular, IOKR is recognized as the current cutting-edge method for metabolite identification due to the following advantages: (i) structures (e.g. featureinteraction in the molecular fingerprint vectors) in the output can beincorporated into the learning model by the kernel defined in the
output space, leading to accuracy improvement; (ii) fingerprints are
simultaneously predicted by the learned model, rather than being
considered as a set of separate tasks, resulting in faster computation.
One can take structures of the metabolites into account by usinggraph kernels (path, shortest-path and graphlet kernels) or kernels
defined on molecular fingerprints. It is also known that kernels
based on fingerprint vectors obtained the best performance (Brouard
et al., 2016). However, a limitation of using molecular fingerprints
as the intermediate representation vectors is that they are generalpurpose and very large in size to encode all possible substructuresand chemical properties related with metabolites. Consequently,
such vectors are neither necessarily specific to any task nor data, andtherefore redundant in the sense that these vectors might contain

information irrelevant to the task, resulting in limited predictive performance. Moreover, the large size of fingerprints causes slow prediction in the first step of the above two steps.
Generally, in machine learning, deep learning has been provensuccessful recently in many application domains. Deep learning isuseful for regular data, say a table, in which rows are instances andcolumns are features, and vice versa. However, semistructured data,
particularly graphs, for example, chemical (or biological) molecules,
which are irregular types of data, are difficult to be used with deeplearning. A number of research efforts have been devoted to applying deep learning to semistructured data, proposing models to learn
representations of graphs, such as Duvenaud et al. (2015), Li et al.
(2015) and Nguyen et al. (2017). Importantly, Gilmer et al. (2017)
showed that a lot of research on graphs can be formulated in a unified model, namely message passing neural network (MPNN), withthe following three components: message passing, update and readout functions. In other words, one way of defining such functions
results in a different model for learning graphs. Furthermore,another attractive property of MPNN is that it allows to learn
meaningful representations specific to each task for graphs in an
end-to-end manner.
We propose a powerful machine learning framework for metabolite identification, named ADAPTIVE, which has two subtasks:(i) learning a mapping from structures to molecular vectors and(ii) learning a mapping from spectra to molecular vectors. Figure 2
shows a schematic picture of ADAPTIVE, where the left and rightblue boxes correspond to the first and second subtasks, respectively.
In Subtask 1, ADAPTIVE learns a model to generate molecular vectors for metabolites using their chemical structures, where these vectors are specific to both data and the task of metabolite identification,and therefore nonredundant. The model in Subtask 1 is parameterizedby MPNN for mapping metabolite structures to the molecular vectors. The main contribution of this article is in the Subtask 1, that is,
to learn the correspondence between given pairs of spectra and structures for metabolites.
Thus, the parameters of MPNN are trained so that the correlation between the spectra and the vectors mapped from the structures is maximized. We use Hilbert-Schmidt Independence Criterion(HSIC, Gretton et al., 2005) for evaluating the correlation, due to its
theoretically nice properties and kernel-based calculation.
Specifically, we formulate an objective function for the maximization problem through HSIC and solve this problem to have the best
molecular vectors adapted to given data. For Subtask 2, ADAPTIVE
uses IOKR to learn a mapping from spectra to molecular vectors
generated by the Subtask 1.
We emphasize that the key difference between ADAPTIVE andthe original IOKR is that IOKR uses ‘manually designed’ fingerprints, which are large in size, possibly redundant and nonspecific tometabolite identification (and given data), while ADAPTIVE learns
representations for metabolites from given data, as molecular vectors, resulting in that the molecular vectors generated by
ADAPTIVE are data-driven and concise.
In order to validate the performance of ADAPTIVE, we conducted
extensive experiments using a benchmark data. Experimental results
showed the following two main advantages of ADAPTIVE over existing methods, including the original IOKR:•

Predictive performance

ADAPTIVE achieved the best performance, followed by IOKR,CSI:FingerID and FingerID. For example, the top-20 accuracy of
ADAPTIVE was 78.52% with the parameters of Gaussian kernel,

Downloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019

Fig. 1. Example MS spectrum from Human Metabolome Database (Wishart
et al. 2013) for 1-Methylhistidine (HMBD00001), with the corresponding chemical structure (top-left) and peak list (top-right)

i165

i166

D.H.Nguyen et al.

ALIGNF and molecular vector size of 300. On the other hand,
IOKR, CSI:FingerID and FingerID achieved 74.79%, 73.07% (or68.20%) and 58.17%, respectively, using Gaussian kernel (for
IOKR) and ALIGNF. The top-k accuracy was computed by the average over all trials of 10-fold cross-validation (CV), and so the performance advantage of ADAPTIVE was significant and very clear.
•

Computational efficiency for prediction

Under the same experimental setting, ADAPTIVE was four toseven times faster than IOKR, which was already known as the fastest method. We can then say that ADAPTIVE is the current fastest
method while keeping the highest predictive performance for metabolite identification.

2 Related work
As mentioned in the Introduction section, fingerprint prediction isimportant in supervised learning for metabolite identification, because we can retrieve metabolite candidates more reliably if fingerprints are predicted more accurately. For fingerprint prediction,
kernel learning has been shown to be the most powerful approach.
For example, a typical approach, FingerID (Heinonen et al., 2012)
uses probability product kernel (PPK, Jebara et al., 2004), which
can be directly computed from spectra and runs support vector machine with this kernel for solving fingerprint prediction as a classification problem. CSI:FingerID (Dührkop et al., 2015), an extensionof FingerID, uses not only spectra but also fragmentation trees (FTs,
Rasche et al., 2011) as input to generate kernels over spectra and
FTs, which are then combined via multiple kernel learning (MKL,
Gönen and Alpaydin, 2011). FTs may capture structural information behind spectra which is missing in the approach of FingerID.
This is the motivation of CSI:FingerID. However, the computational
cost for converting FTs from MS/MS spectra is very expensive, leading to heavy computational load, which causes a problem particularly in prediction. Thus, we can say that kernel-based supervised

learning, particularly complex kernels, have a computation issue, regardless of high performance in prediction. On the other hand, asparse learning model, namely SIMPLE (Nguyen et al., 2018b), considers a simpler function than kernels for fingerprint, while interactions of peaks in spectra can be incorporated into learning models
explicitly. SIMPLE achieved a comparable performance against
kernel-based learning, reducing the computational cost drastically.
A key point of SIMPLE is to take advantage of sparsity of spectra,
which results in faster prediction and interpretability, showing clear
advantages over kernel-based methods.
Among the series of kernel-based approaches, IOKR (Brouard
et al., 2016) has been shown to outperform the previous methods, interms of both predictive performance and computational speed.
It learns a mapping from spectra, i.e. input X, to molecular fingerprints (or structures behind fingerprints), i.e. output Y. In orderto do this mapping, IOKR defines kernels to encode similarities in
the input space (e.g. spectra and/or FTs) and the output space (molecular fingerprints or structures). Then, the advantage of IOKR
comes from the following two points: (i) unlike previous kernelbased methods, IOKR handles the structured output space by the
kernel defined for the output, which improves the predictive performance; (ii) IOKR simultaneously predicts fingerprints rather thanconsidering fingerprint prediction as a set of separate tasks, leading
to an efficient computation in prediction. Some part (mapping fromspectra to feature vectors) of IOKR is a part of ADAPTIVE, and sofurther technical details of the corresponding part of IOKR is
described more in Section 3.
Conventionally, molecular fingerprints for fingerprint prediction
have been manually designed feature vectors to encode a predefined
set of substructures or chemical properties, which are possibly foundin metabolites. However, recently, machine learning-based (or datadriven) algorithms for generating fingerprints have been proposed.
A typical approach is neural fingerprint (NFP, Duvenaud et al.,2015), which takes graphs with arbitrary sizes and shapes as inputs.
NFP uses the idea of graph convolution, an extension of convolution
operation from multidimensional arrays, like images or texts, toDownloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019

Fig. 2. Overview of ADAPTIVE for metabolite identification. ADAPTIVE has two components: (i) Subtask 1: estimates parameters of a function mapping metabolites from structures to molecular vectors, given a set of spectra-structure pairs; (ii) Subtask 2: learns a function mapping from spectra to molecular vectors (generated by Subtask 1), given a set of spectrum-vector pairs

Learning adaptive molecular vectors for metabolite identification

3 Materials and methods
3.1 ADAPTIVE: overview
We first introduce the framework of ADAPTIVE for metabolite
identification. This is also the general framework of approaches
using machine learning for metabolite identification. It has two subtasks. Subtask 1: learning a function which maps metabolites fromtheir structures to molecular vectors and Subtask 2: learning a function which maps metabolites from spectra to the vectors generated
in Subtask 1. Figure 2 shows an illustration of the entire frameworkof ADAPTIVE. In this figure, the left and right blue boxes correspond to Subtasks 1 and 2, respectively.
For Subtask 1, given pairs of metabolite structure-spectrum, weestimate parameters of a function which maps metabolites fromtheir structures to molecular vectors by maximizing the correlation
between the vectors mapped from the structures and also the corresponding spectra. In more detail, we model the mapping function by
MPNN and evaluate the correlation between the vectors and spectraby using HSIC due to the computational simplicity and provably
theoretical properties of HSIC. For Subtask 2, we simply borrow thecorresponding part of IOKR to learn a function mapping metabolites from spectra to vectors generated by Subtask 1.
We explain these two subtasks in the following subsections,being followed by the subsection on kernels we used in ADAPTIVE.

3.2 Subtask 1: learning molecular vectors formetabolites via HSIC
For this subtask, we need to estimate a function to map metabolites
from structures to molecular vectors, given spectrum-structure pairs.
For this problem, we use MPNN as the mapping function, which
can extract meaningful representation for graphs (molecules for our
problem) by supervised learning from training data. That is, MPNN
requires labeled training data, which are, however, unavailable forthis subtask. Then we manage this problem by taking advantage of
given spectrum-structure pairs. We estimate parameters of MPNN
by using the idea of maximizing the correlation between the given
spectra and vectors (mapped from structures). The correlation isevaluated by HSIC. We describe the detail of MPNN, HSIC andrelated optimization procedures in the following subsections.

3.2.1 Message passing neural network
MPNN is a framework, which takes graphs of arbitrary sizes andstructures as inputs, to learn their representation vectors at different
levels (i.e. nodes, subgraphs and the whole graph) in a supervisedmanner (Gilmer et al., 2017). A key advantage is that MPNN allows
to learn features specific to the given task from the given data.
Below, we explain the procedure of MPNN.
First let G be an undirected graph, and v and vw be a node
(atom in molecules) and an edge (bond in molecules), respectively.
Each node v is assigned with state vectors at different levels, where
each level represents a substructure (or subgraph) rooted at the corresponding node, denoted by hrv , where r shows a level. We can compute state vector hrv as well as message mrv in a hierarchical manner,by using the following two functions: message passing (1) andupdate (2):
X
r
mrþ1
¼
HeðvwÞ
hrw ;(1)v
w2N ðvÞ

hrþ1¼ gðhrv þ mrþ1
v
v Þ;

(2)

where N ðvÞ denotes the set of neighbors of node v in graph G; e(v,w) indicates the type of edge between two nodes v and w (this edgertype is like a single, double, triple or aromatic bond); HeðvwÞ
is a(square) weight matrix to be learned, specific to the edge type e(vw)
at the rth level; g is a nonlinear activation function (e.g. ReLU or
sigmoid).
Intuitively, the message passing function (1) on node v plays therole of collecting information from the neighbors of node v and update function (2) on node v is to update the state of node v based on
the collected information and the former state of node v. Thus, byapplying two functions (1) and (2) multiple times, the updated features at node v (e.g. hrþ1v ) can be used to represent a certain numberof substructures with the root of node v. Then, the values for theseseries of substructures can be used to generate a vector at node v
with different levels (sizes) of substructures. Figure 3 shows a schematic and illustrative picture of this procedure [Fig. 3 is from
Nguyen et al. (2017)].
After obtaining the state vectors of substructures rooted at nodev, i.e. hrv , we have the readout phase to combine all vectors at different levels into a single representation vector of the whole molecule(namely, NFPs). Figure 4 shows a schematic picture of summing up
the state vectors at different levels. As in Duvenaud et al. (2015), we
adopt the softmax operation on the states and then perform linear
projections (parameterized by different weight matrices Wr) and finally sum them up to obtain a single vector over different levels
which represents the whole graph. In short, the molecular vector forthe entire molecule can be written as following:XX
softmaxðWr hrv Þ:
(3)
r

v

We note that operations are all differentiable with respect to parameters, which makes learning the parameters possible, given an objective function, by a stochastic or minibatch gradient descentalgorithm. Algorithm 1 shows a pseudocode of the procedure of
repeating the message passing and update functions.

3.2.2 HSIC-based objective function
We estimate parameters of MPNN by maximizing the correlation(dependency) between given spectra and molecular vectors. A lot of
measures can be used to evaluate and estimate the correlation, while
we use HSIC due to its theoretically sound properties. More

Downloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019graph structures. NFP is then trained in a supervised manner byusing available labels, such as log mol/L for solubility, EC50 for
drug efficacy. Finally, NFP results in fingerprint vectors (formolecules) specific to given task and data. An extension of NFP is
for unsupervised (as well as semisupervised) settings to learn representations of molecular graph without labels (Nguyen et al., 2017),
since label information can be experimentally obtained andprecious.
More recently, Gilmer et al. (2017) showed that several graphconvolution-based models, including NFP, Gated Graph Neural
Networks (Li et al., 2015), spectral graph convolutional network(Kipf and Welling, 2016), etc., can be formulated in an unified
model, namely MPNN, with the following three functions: message
passing, update and readout. A key advantage of MPNN is thatdefining the above components generates a proper model for learning graphs, depending on a given task. Also, another advantage of
MPNN as well as other neural network-based methods in this paragraph is that they adopt differentiable operations, and thus theirparameters can be effectively trained by using a stochastic gradientdescent algorithm.

i167

i168

D.H.Nguyen et al.

Algorithm 1. Message Passing Neural Network (MPNN).

Fig. 4. Representation vectors of substructures, which are rooted at nodes,
are computed from the input graph by the message passing and update functions. These functions contribute to computing the molecular representation
vector of the whole molecule

importantly, estimation of HSIC is based on kernel calculation,
which can effectively deal with the uncertainty of peaks in spectra
caused by measurement errors.
Formally, we are given dataset D ¼ ðX ; YÞ ¼ fðxi ; yi Þgni¼1 , where
xi ; yi are spectrum and molecular structure, respectively, of the ith
metabolite. First, for the spectra, i.e. x, we consider kernels which
combine spectra with FTs, namely kðxi ; xj Þ. We describe the detailof the kernels for spectra in Section 3.4. Then, given the kernel over
X is fixed, the goal is to learn the function / : Y7!F d from D suchthat the correlation between the input and output is maximized. The/ðyÞ is the output of MPNN (or molecular vectors) which belongs
to space F d . The linear kernel function induced by this space can be
written as follows:lðyi ; yj Þ ¼ h/ðyi Þ; /ðyj Þi(4)To evaluate the correlation between spectra and molecular vectors (output of MPNN), we use an unbiased empirical estimate of
HSIC (Gretton et al., 2005), which can be given as follows:

1: Inputs:
minibatch of molecular structures Yb ¼ fyi gBi¼1 , radius R
weight matrices of edges: H11 ; H12 ; . . . ; HR4,weight matrices of readout function: W1, W2,. . ., WR
2: Outputs:
molecular vectors /ðYb Þ
3: for i
1 to B do
4:
for each atom v in yi do
5:hv initial hidden rep. vector of v " atom feature6:
end for7:/i0d " Initialize each molecular vector with azero vector8:
for r
1 to R do
9:for each node v in yi do
P
10:
mrþ1
¼ w2N ðvÞ Hrvw hrw " message function
v
11:
hrþ1
¼ gðhrv þ mrþ1
" update function
v
v Þ
12:
/i ¼ /i þ softmaxðWrþ1 hrþ1v Þ " readout function
13:
end for14:
end for
15: end for
16: /ðYb Þ ¼ ½/1 ; /2 ; . . . ; /B 

uHSICðX; YÞ ¼

1
1> Kn 1n 1>
n Ln 1n½traceðKn Ln Þ þ nnðn  3Þðn  1Þðn  2Þ2
n Ln 1n ;
1>
K

n2 n

(5)

where Kn ¼ Kn  diagðKn Þ denotes the kernel matrix for the set of n
spectra X with diagonal elements set to zero; 1n is a vector of 1 s ofn dimensions. Likewise Ln ¼ Ln  diagðLn Þ, where Ln is the kernel
matrix of n molecular vectors output by MPNN. By arranging termsin (5), we can rewrite (5) as the objective function to learn parameters as follows:uHSICðX ; YÞ ¼ traceðSn Ln Þ(6)Downloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019

Fig. 3. Message passing and update functions are used to represent rooted substructures in a hierarchical manner. At the first level (left-most graph), each nodeis represented by feature vector, with only information of the node itself. We note that by repeatedly applying message passing and update functions (from left toright), more neighboring information are incorporated. For example, the updated feature (second level) has information on nodes 3 and 5, and then third levelhas that on nodes 2 to 5. Finally, the whole graph is covered

Learning adaptive molecular vectors for metabolite identification

i169

where
(7)

However, directly optimizing (6) is prohibitively expensive incomputation, particularly for large-scale data, since the complexity
reaches O(n2), both in space and time. In order to overcome thislimitation, following Zhang et al. (2018), we disjointly divide samðbÞ ðbÞ
n=B
ples ðX ; YÞ into n/B blocks with the size of B, ffðxi ; yi ÞgBi¼1 gb¼1
and then apply HSIC on each block independently. An empirical estimate of the unbiased block HSIC can be defined by:
n=B

ubHSICðX ; YÞ ¼

1 X
 b Þ;
traceðSb L
n=B b¼1(8)

 b is thewhere Sb can be defined by a similar manner to (7), and L
kernel matrix for the bth block.
Furthermore, in order to avoid the effect by biased partition of
the dataset, following Yamada et al. (2018), we repeat shufflingdataset T times, compute ubHSIC on each permutation and take theaverage over them. HSIC by this procedure is known as bagging
block HSIC, which can be written as follows:
ubHSICðX ; YÞ ¼

n=B
T
1X
1 X
 t;b Þ;traceðSt;b L
T t¼1 n=B b¼1(9)

We use (9) as objective function J to learn parameters.
3.2.3 Optimization algorithm
An advantage of objective function (9) is that we can use the gradientdescent (minibatch gradient descent) for estimating parameters of
MPNN. We here explain details on how to conduct the minibatch gradient descent procedure for the HSIC-based loss, which has three steps.
Step 1: Feed forward and loss calculation.
For samples of size n, at each iteration, we perform random permutation and then split all samples into batches, where the size ofeach batch is B. Batches are sequentially fed into MPNN. The output of MPNN for the bth batch at the tth iteration is denoted by/ðYt;b Þ ¼ ð/ðy1t;b Þ; /ðy2t;b Þ; . . . /ðyt;bB ÞÞ. Then using these outputs, theobjective function on the whole samples can be calculated as in (9).
Step 2: Gradient calculation of the loss layer.
As we can compute the loss directly with the output of MPNN
(i.e. /ðYt;b Þ), we need to compute the gradient of J with respect to/ðYt;b Þ. Suppose that the output of MPNN is already normalized,
i.e. /ðyÞ> /ðyÞ ¼ 1 for all y 2 Y, the gradient can be obtained by thefollowing:@JB
S /ðYt;b Þ¼@/ðYt;b Þ Tn t;bAlgorithm 2. Learning molecular representation vectors via
HSIC.
1: Inputs:
set D ¼ fðxi ; yi Þgni¼1 of spectra-structure pairs,
T: number of iterations, B: size of minibatch
2: Outputs:
h ¼ fH11 ; H12 ; . . . ; HR
4 ; W1 ; W2 ; . . . ; WR g [ fhv jv 2 set ofatomsg3: for t
1 to T don=B
4: Dt ¼ ffðxit;b ; yit;b ÞgBi¼1 gb¼1
" shuffled and split
5: for b
1 to B do
6:
Yt;b ¼ fyit;b gBi¼1 ; Xt;b ¼ fxit;b gBi¼1
7:Ft;b ¼ /ðYt;b Þ " Call Algorithm 1
8:
St;b is calculated from Xt;b by (7)9:Jt;b ¼ traceðSt;b F>
t;b Ft;b Þ
10:gradient of loss layer
St;b Ft;b
11:
Gradh is calculated by chain rule12:hh  cGradh " Update the whole parameters
13:
end for
14: end for

explain two technical reasons why we use IOKR for this mapping
below: (i) IOKR allows to incorporate the structures behind outputs,
such as feature interactions in molecular vectors, into the learning model,
by which the prediction accuracy can be improved. (ii) Furthermore, allfeatures in molecular vectors are predicted simultaneously, which is notlike separate tasks in prediction. This leads to faster computation.
We now present the technical detail of IOKR below, which has
two consecutive steps.
3.3.1 Step 1: Learning spectra-vectors mapping
Once parameters, i.e. function /, are learned, we convert the structures of metabolites into their molecular vectors to obtain a new setof pairs, fðxi ; /ðyi ÞÞgni¼1 . Now the goal is to find the optimal function h : X ! F d by minimizing the following objective function:h^ ¼ argmin
h2H

n
X

jjhðxi Þ  /ðyi Þjj2F d þ kjjhjj2H ;where k (> 0) is a regularization parameter to prevent overfittingand H is an approximate functional space that contains h; F d is aspace of molecular vectors of dimension d.
By using the representer theorem in Micchelli and Pontil (2005),
optimal solution h^ of (11) can be represented by a linear combination of vector-valued kernels on training set X:(10)

Step 3: Gradient calculation of the MPN and weight update.
Having calculated the gradient of J, i.e. (10), the next step is to compute the gradient of /ðYt;b Þ with respect to model parameters h, name@/ðY Þ
ly @ht;b , to update the whole parameters for each batch at each step.
Algorithm 2 is a pseudocode of the entire algorithm of learningparameters of MPNN.

3.3 Subtask 2: learning a mapping from spectra tomolecular vectors by IOKRFor Subtask 2, we use IOKR. That is, we learn a mapping from spectra
to molecular vectors generated in Subtask 1 by using IOKR. Again, we

(11)

i¼1

^ iÞ ¼hðxnX

Kn ðxi ; xj Þcj ;

(12)

i¼1

where ci ði ¼ 1; . . . ; nÞ are vectors in F d ; Kn is an operator-valued
kernel, defined on spectra X, satisfying certain constraints (seeMicchelli and Pontil, 2005). As dimensionality d of space F d is finite, the kernel is a matrix with the size of d  d.
^ i Þ in (11) with (12), ci ði ¼ 1; . . . ; nÞ can be estiBy replacing hðx
mated in the following:vecðCn Þ ¼ ðkInd þ Kn Þ1 vecð/ðYn ÞÞ;(13)where Cn ¼ ðc1 ; c2 ; . . . ; cn Þ and /ðYn Þ ¼ ð/ðy1 Þ; /ðy2 Þ; . . . ; /ðyn ÞÞare both matrices with the size of d  n, and vec(.) is the

Downloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019

"
#
>

1
1n 1>
2
n Kn 1n 1n
n
Kn þ
1n 1>
K

Sn ¼
n
nðn  3Þðn  1Þðn  2Þ n  2

i170

D.H.Nguyen et al.

3.3.2 Step 2: Candidate retrieval
Given mapping h^ learned in Step 1, we now turn to the problem offinding the output metabolite in the database which corresponds tothe query spectrum x. To this end, we search metabolite y in the listof given candidates Y  , such that the squared distance between /ðyÞ^and hðxÞ
can be minimized:^
f ðxÞ ¼ argmin jjhðxÞ
 /ðyÞjj2F d

(14)

y2Y 

Considering that the output kernel is normalized and theoperator-valued kernel keeps Kn ðx; x0 Þ ¼ kðx; x0 Þ  Id , the optimal
solution of f ðxÞ can be estimated as the following:f^ðxÞ ¼ argmax lðY; yÞ> ðkIn þ Kn Þ1 kðX; xÞ;

(15)

y2Y 

2

3
2
3
lðy1 ; yÞkðx1 ; xÞ
6
7
6
7
..
..
where lðY; yÞ ¼ 4
5 and kðX; xÞ ¼ 4
5 are column.
.
kðxn ; xÞlðyn ; yÞvectors.
Practically, the values given by objective function (15) are used asscores for ranking candidate metabolites in Step 2: candidate retrieval.

3.4 Kernels
ADAPTIVE uses kernels for the input and output.
3.4.1 Kernels for input
A various types of kernels are already defined and used for the input
from MS/MS spectra. These kernels are typically divided into the following two groups: (i) kernels defined for spectra such as PPK (Jebara
et al., 2004) and (ii) kernels defined for FTs (Rasche et al., 2011).
Details on these kernels can be found in Dührkop et al. (2015).
In fact, Dührkop et al. (2015) suggested 24 different input kernels.
ADAPTIVE combines these input kernels into a single kernel through
MKL (Gönen and Alpaydin, 2011). ADAPTIVE uses two options for
MKL: (i) UNIMKL (uniform MKL): assigns the same weights to allcomponent kernels, and (ii) ALIGNF: uses weights over kernels to
combine. That is, in ALIGNF, weights over component kernels are
optimized (trained) by maximizing the centered kernel alignment between the combined kernel and the target kernel defined on the molecular vectors, which generate trained parameters (model).
3.4.2 Kernels for output
After learning parameters (model) to generate the molecular vectors
for structures, we define kernels for output Y by directly computing
kernels on the corresponding molecular vectors. In our experiments,
we consider the following two typical kernels:••

Linear kernel: lðy; y0 Þ ¼ /ðyÞ> /ðy0 Þ.
Gaussian kernel: lðy; y0 Þ ¼ expðcjj/ðyÞ  /ðy0 Þjj2 Þ,
where y and y0 are molecular structures in Y.

4 Experimental results
4.1 Dataset and evaluation measures
We used a benchmark dataset in Brouard et al. (2016) to evaluate
ADAPTIVE and compare with existing methods. The dataset

Table 1. Parameter values used for experiments
Notations Parameter
T
B
R
d
m

Values#epoch100
Batchsize
100#updates
6#dim of molecular vectors 100,200,300#dim of atom feature50#atom types
12 (C, O, N, P, S, etc.)#bond types
4 (single, double, triple, acromatic)

consists of 4138 MS/MS spectra extracted from the GNPS (Global
Natural Products Social) public spectra library (https://gnps.ucsd.
edu/ProteoSAFe/libraries.jsp).
To compare ADAPTIVE with existing methods, we used thesame setting for all competing methods. Specifically we used 10-fold
CV, and the results are averaged over all 10-folds. The performancewas checked by the top-k accuracies (where k ¼ 1, 10, 20), which is
the ratio of the number of the cases that the true structures areranked at lower than or equal to k to the number of all cases. Also
the speed was checked by computation time for prediction, measured by milliseconds per example (ms/example).
Hyperparameters, such as regularization parameter k and parameter c of the output kernel, were chosen by using leave-one-out CV oneach training fold. For prediction in ADAPTIVE, at the retrieval stage,^
given test example x, we computed the molecular vectors of x, hðxÞ[see (11)] and those of all candidates /(y) (see Algorithm 1). These candidates including the correct molecular structure of test example x^were ranked, according to their distances to hðxÞ(from the smallest to
the highest). These ranked candidates were used for computing the
top-k accuracy. Table 1 shows a set of parameter values, which wereused to train MPNN of generating molecular vectors. State vectors ofidentical atoms at the lowest (atomic) level were initialized with thesame random vector sampled from the standard normal distribution
and updated during the training stage.
All experiments were performed on a server with 2.7 GHz Intel
Core i5 CPU and 8GB memory. The code was written in Python andMatlab with the support of the Chainer framework (Tokui et al.,2015).

4.2 Performance results
4.2.1 Predictive performance
We compared the predictive performances of ADAPTIVE with three
existing methods: FingerID (Heinonen et al., 2012), CSI:FingerID(Dührkop et al., 2015) and IOKR (Brouard et al., 2016) in terms ofthe top-k accuracy (k ¼ 1, 10 and 20). Table 2 shows the top-k accuracies of the competing methods with UNIMKL and ALIGNF for
MKL and linear and Gaussian kernels for the output kernel, changing k from 1 to 20 and also changing the size of fingerprints from100 to 300 (for ADAPTIVE only). This table first shows that
ADAPTIVE achieved the best performance, being followed by
IOKR, CSI:FingerID and FingerID. For example, ADAPTIVE with
ALIGNF, Gaussian kernel and the fingerprint size of 300 achieved
31.03% for k ¼ 1, while IOKR with ALIGNF and Gaussian kernel
was 29.59% and CSI:FingerID with ALIGNF was 28.84% or
24.82%. That of Finger: ID was only 17.74%. Interestingly, for
k ¼ 1, the performance advantage of ADAPTIVE against IOKR was
rather slight, while k ¼ 10 and 20, ADAPTIVE outperformed IOKR
much more clearly, with the difference of around 3–5% under thesame condition for the two methods.

Downloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019vectorization of the input matrix, where the output is a vector
obtained by repeatedly stacking each column of the input matrix on
the top of the next column.

Learning adaptive molecular vectors for metabolite identification
Table 2. Comparison of the top-k accuracy (k ¼ 1, 10 and 20) of
FingerID, CSI:FingerID, IOKR and ADAPTIVE

FingerID
CSI:FingerID
unit
CSI:FingerID
mod
Platt
IOKR linear
ADAPTIVE
linearIOKRGaussian
ADAPTIVE
Gaussian

Vec.
size

MKL

Table 3. Computation time for prediction by ADAPTIVE and IOKR
MethodMol. vec. size

Accuracies (mean/SD %)prediction time (ms/example)
Linear

Top 1

Top 10Top 202765 None2765 ALIGNF

17.74
24.82

49.59
60.47

58.17
68.20

2765 ALIGNF

28.84

66.07

73.07

2765 UNIMKLALIGNF
100 UNIMKLALIGNF
200 UNIMKLALIGNF
300 UNIMKLALIGNF2765 UNIMKL

30.58/2.23
28.54/2.54
29.42/2.83
29.19/3.21
29.57/3.96
29.11/3.45
30.22/3.47
30.61/3.23
30.66/2.34

65.99/2.46
65.77/2.39
70.01/2.79
69.52/2.89
69.38/3.05
69.53/2.52
70.48/2.72
70.51/2.52
66.51/2.87

73.53/2.47
73.19/3.11
77.48/2.98
77.64/3.23
76.95/2.98
77.56/2.43
78.18/2.67
78.23/2.75
73.94/2.54

ALIGNF
100 UNIMKLALIGNF
200 UNIMKLALIGNF
300 UNIMKLALIGNF29.59/2.58
29.47/3.21
29.37/3.21
29.44/3.86
28.98/3.32
30.31/3.48
31.03/3.40

66.13/2.09
70.01/2.83
69.91/2.64
69.84/2.78
69.65/2.71
71.10/2.73
70.89/2.74

73.62/1.85
77.51/2.11
77.48/2.33
77.08/2.95
77.15/2.74
78.51/2.65
78.52/2.52

Note: The highest value (indicating the most accurate prediction) are inboldface for each k.

We used one-sided paired t-test to verify if the differences
between ADAPTIVE and IOKR are statistically significant. For example, considering the top 10 accuracy with Gaussian kernel and
ALIGNF, the calculated P-value was P ¼ 0.0012. Since it is less than
the significance level of a ¼ 0.01, we can claim the statistical significance of the advantage of ADAPTIVE in terms of the top 10 accuracy over IOKR under Gaussian kernel and ALIGNF. We conclude
that the performance advantage of ADAPTIVE was confirmed bychecking a larger number of top candidates. Another finding is theperformance difference between linear and Gaussian kernels wasvery slight (almost nothing) for ADAPTIVE under the same otherconditions. This is also true with the settings of UNIMKL and
ALIGNF, the performance for them was rather the same. However,the size of fingerprints strongly affected the performance in the sensethat a larger size of fingerprints achieved a higher performance. Insummary, ADAPTIVE clearly outperformed competing methods
with, for example, for k ¼ 20, the difference of 3–5%, which is very
sizable.
4.2.2 Computation time for prediction
IOKR was already shown to be faster than previous kernel-based
methods in prediction (Brouard et al., 2016). Thus, we consider
only IOKR as a competing method for examining computational efficiency. Table 3 shows the computation time of ADAPTIVE and
IOKR with linear and Gaussian kernels for prediction. The computation time was averaged over the 10-fold CV. This table shows that
ADAPTIVE was significantly faster than IOKR. Specifically, underboth linear and Gaussian kernels, ADAPTIVE with the fingerprint
size of 100 was four to seven times faster than IOKR. This is because
molecular vectors by ADAPTIVE are much more precise and adaptive to given data than those used in IOKR.

IOKRADAPTIVE

2765
100
200
300

140.22
20.32
39.88
54.14

Gaussian
3352.4802.6
844.331071.8

Note: The smallest values (indicating the fastest) were in boldface for linear
and Gaussian kernels.

4.3 Case study
To understand the results obtained by ADAPTIVE more, in theobtained molecular vectors, we examined substructures rooted at
atoms, which activated several example features most. As shown in
Section 3.2.1, each substructure rooted at an atom is represented by astate vector and contributes to computing the molecular vector of thewhole molecule. Then, given a feature, we can estimate the contribution of each substructure by simply computing the softmax value fromthe corresponding state vector. We use these values of substructures asscores to rank substructures to activate the given feature.
Figure 5 shows three example features (#2, #39 and #83). For eachfeature, we show three substructures with the highest scores (each scoreis shown above the substructure). The first row shows three substructures which activated feature #2 most. Interestingly, we can see thatthese substructures share a further smaller, similar group of atoms: O,
P and S (highlighted in blue). Similarly, the second row shows threesubstructures sharing a group of atoms: O and N, where these substructures activated feature #39 most. Also the third row shows substructures which activated feature #83, all having atom: Cl. Thus,
Figure 5 shows that each feature of ADAPTIVE is activated by multiple
different substructures sharing some similar properties, which must be
important in data and probably for prediction. In contrast, each featurein regular molecular fingerprints is activated by only one predefined
substructure. In summary, from this case study, learned features of
ADAPTIVE are more concise and specific to the task of metabolite
identification than regular molecular fingerprints, leading to the advantage of predictive performance and computation time.

5 Discussion and conclusion
Supervised learning for metabolite identification uses fingerprints asintermediate representation vectors between spectra and metabolites,
while such fixed vectors are too redundant to cover all possible substructures and chemical properties in metabolites, causing limitationsin predictive performance and high computational costs. To overcome
this problem, we have proposed ADAPTIVE, which generates representations of metabolites specific to given spectrum-structure pairs.
ADAPTIVE learns a model to generate molecular vectors for metabolites, which is parameterized by a MPNN over given molecular structures and trained through optimizing the objective function to
maximize the correlation between molecular vectors and corresponding
spectra. Our empirical validation of ADAPTIVE with the benchmark
dataset showed the advantage of ADAPTIVE over existing methods
including IOKR, the current cutting-edge method, both in predictive
performance and computation time for prediction.
A drawback of ADAPTIVE would be interpretability, because
structural information is implicitly encoded in compact vectors in
ADAPTIVE and cannot be made explicit easily. In metabolite identification, it would be desirable to connect the set of peaks to the

Downloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019

Method

i171

i172

D.H.Nguyen et al.

corresponding substructures/chemical properties of metabolites(Nguyen et al., 2018b). Developing a model with such interpretability would be interesting future work.

Funding
D.H.N. has been supported in part by Otsuka Toshimi scholarship and JSPS
KAKENHI [grant number 19J14714]. C.H.N. has been supported in part by
MEXT Kakenhi 18K11434. H.M. has been supported in part by JST ACCEL[grant number JPMJAC1503], MEXT Kakenhi [grant numbers 16H02868
and 19H04169], FiDiPro by Tekes (currently Business Finland) and AIPSE
program by Academy of Finland.
Conflict of Interest: none declared.

References
Brouard,C. et al. (2016) Fast metabolite identification with input output kernel regression. Bioinformatics, 32, i28–i36.
de Hoffmann,E. and Stroobant,V. (2007). Mass Spectrometry, Principles andApplications. 3rd edn. John Wiley & Sons, Hoboken, New York.
Dührkop,K. et al. (2015) Searching molecular structure databases with tandem
mass spectra using CSI:FingerID. Proc. Natl. Acad. Sci., 112, 12580–12585.
Duvenaud,D.K. et al. (2015). Convolutional networks on graphs for learning
molecular fingerprints. In: Cortes,C., Lawrence,N.D., Lee,D.D.,
Sugiyama,M., and Garnett,R. (eds.) Proceedings of the 28th International
Conference on Neural Information Processing Systems, Vol. 2. Curran
Associates, Inc., Montreal, Canada, pp. 2224–2232.
Gilmer,J. et al. (2017). Neural message passing for quantum chemistry. In:
Precup,D. and Teh,Y.W. (eds.) Proceedings of the 34th International Conference
on Machine Learning, Volume 70 of Proceedings of Machine Learning Research.
International Convention Centre, PMLR, Sydney, Australia, pp. 1263–1272.
Gönen,M., and Alpaydin,E. (2011) Multiple kernel learning algorithms.
J. Mach. Learn. Res., 12, 2211–2268.
Gretton,A. et al. (2005). Measuring statistical dependence with
Hilbert-Schmidt norms. In: Proceedings of the 16th International
Conference on Algorithmic Learning Theory, ALT’05. Springer-Verlag,
Berlin, Heidelberg, pp. 63–77.

Heinonen,M. et al. (2012) Metabolite identification and molecular fingerprint
prediction through machine learning. Bioinformatics, 28, 2333–2341.
Jebara,T. et al. (2004) Probability product kernels. J. Mach. Learn. Res., 5,
819–844.
Kipf,T.N. and Welling,M. (2016). Semi-supervised classification with graphconvolutional networks. arXiv preprint arXiv: 1609.02907.
Li,Y. et al. (2015) Gated graph sequence neural networks. CoRR, abs/1511.05493.
Micchelli,C.A. and Pontil,M.A. (2005) On learning vector-valued functions.
Neural Comput., 17, 177–204.
Nguyen,D.H. et al. (2018a). Recent advances and prospects of computational
methods for metabolite identification: a review with emphasis on machine learning approaches. Brief. Bioinf. doi: 10.1093/bib/bby066. [Epub ahead of print].
Nguyen,D.H. et al. (2018b) Simple: sparse interaction model over peaks ofmolecules for fast, interpretable metabolite identification from tandem mass
spectra. Bioinformatics, 34, i323–i332.
Nguyen,H. et al. (2017). Semi-supervised learning of hierarchical representations of molecules using neural message passing. CoRR, abs/1711.10168.
Rasche,F. et al. (2011) Computing fragmentation trees from tandem
mass spectrometry data. Anal. Chem., 83, 1243–1251. PMID:
21182243.
Tokui,S. et al. (2015) Chainer: a next-generation open source framework fordeep learning. In: Proceedings of Workshop on Machine Learning Systems(LearningSys) in the Twenty-Ninth Annual Conference on Neural
Information Processing Systems (NIPS), Vol. 5, pp. 1–6.
Vaniya,A. and Fiehn,O. (2015) Using fragmentation trees and mass spectral
trees for identifying unknown compounds in metabolomics. Trends Analyt.
Chem., 69, 52–61.
Wishart,D.S. (2007) Current progress in computational metabolomics. Brief.
Bioinf., 8, 279–293.
Wishart,D.S. et al. (2013) HMDB 3.0—the human metabolome database in
2013. Nucleic Acids Res., 41, D801–D807.
Yamada,M. et al. (2018). Post selection inference with kernels. In: Storkey,A. andPerez-Cruz,F. (eds.) Proceedings of the Twenty-First International Conference on
Artificial Intelligence and Statistics, volume 84 of Proceedings of Machine
Learning Research. Playa Blanca, PMLR, Lanzarote, Canary Islands, pp.
152–160.
Zhang,Q. et al. (2018) Large-scale kernel methods for independence testing.
Stat. Comput., 28, 113–130.

Downloaded from https://academic.oup.com/bioinformatics/article-abstract/35/14/i164/5529113 by Library of Research Reactor Institute, Kyoto University user on 16 July 2019

Fig. 5. Example features (#2, #39 and #83) and their three substructures (and their scores) which activated the corresponding feature most. Note that three substructures of each feature share a similar group (set) of atoms which are shown in blue