  Metabolites, small molecules that are involved in cellular reactions, provide
a direct functional signature of cellular state. Untargeted metabolomics
experiments usually relies on tandem mass spectrometry to identify the
thousands of compounds in a biological sample. Today, the vast majority of
metabolites remain unknown. Fragmentation trees have become a powerful tool for
the interpretation of tandem mass spectrometry data of small molecules. These
trees are found by combinatorial optimization, and aim at explaining the
experimental data via fragmentation cascades. To obtain biochemically
meaningful results requires an elaborate optimization function. We present a
new scoring for computing fragmentation trees, transforming the combinatorial
optimization into a maximum a posteriori estimator. We demonstrate the
superiority of the new scoring for two tasks: Both for the de novo
identification of molecular formulas of unknown compounds, and for searching a
database for structurally similar compounds, our methods performs significantly
better than the previous scoring, as well as other methods for this task. Our
method can expedite the workflow for untargeted metabolomics, allowing
researchers to investigate unknowns using automated computational methods.
