Scheubert Kerstin, Hufsky Franziska, Rasche Florian, Böcker Sebastian
Chair for Bioinformatics, Friedrich-Schiller-Universität Jena, Jena, Germany.
J Comput Biol. 2011 Nov;18(11):1383-97. doi: 10.1089/cmb.2011.0168. Epub 2011 Oct 28.
Since metabolites cannot be predicted from the genome sequence, high-throughput de novo identification of small molecules is highly sought. Mass spectrometry (MS) in combination with a fragmentation technique is commonly used for this task. Unfortunately, automated analysis of such data is in its infancy. Recently, fragmentation trees have been proposed as an analysis tool for such data. Additional fragmentation steps (MS(n)) reveal more information about the molecule. We propose to use MS(n) data for the computation of fragmentation trees, and present the Colorful Subtree Closure problem to formalize this task: There, we search for a colorful subtree inside a vertex-colored graph, such that the weight of the transitive closure of the subtree is maximal. We give several negative results regarding the tractability and approximability of this and related problems. We then present an exact dynamic programming algorithm, which is parameterized by the number of colors in the graph and is swift in practice. Evaluation of our method on a dataset of 45 reference compounds showed that the quality of constructed fragmentation trees is improved by using MS(n) instead of MS² measurements.
由于无法从基因组序列预测代谢物，因此人们迫切希望能够高通量地从头鉴定小分子。质谱（MS）结合碎裂技术通常用于此任务。不幸的是，此类数据的自动化分析尚处于起步阶段。最近，碎裂树已被提议作为此类数据的分析工具。额外的碎裂步骤（MS(n)）能揭示更多关于分子的信息。我们建议使用MS(n)数据来计算碎裂树，并提出“彩色子树闭包问题”来形式化此任务：在该问题中，我们在一个顶点着色的图中寻找一个彩色子树，使得该子树的传递闭包的权重最大。我们给出了关于此问题及相关问题的可处理性和可近似性的几个负面结果。然后，我们提出了一种精确的动态规划算法，该算法由图中的颜色数量参数化，并且在实际应用中速度很快。在一个包含45种参考化合物的数据集上对我们的方法进行评估表明，使用MS(n)而非MS²测量可以提高构建的碎裂树的质量。
