Back to Search
Start Over
Fast alignment of fragmentation trees.
- Source :
-
Bioinformatics . Jun2012, Vol. 28 Issue 12, pi265-i273. 1p. - Publication Year :
- 2012
-
Abstract
- Motivation: Mass spectrometry allows sensitive, automated and high-throughput analysis of small molecules such as metabolites. One major bottleneck in metabolomics is the identification of ‘unknown’ small molecules not in any database. Recently, fragmentation tree alignments have been introduced for the automated comparison of the fragmentation patterns of small molecules. Fragmentation pattern similarities are strongly correlated with the chemical similarity of the molecules, and allow us to cluster compounds based solely on their fragmentation patterns.Results: Aligning fragmentation trees is computationally hard. Nevertheless, we present three exact algorithms for the problem: a dynamic programming (DP) algorithm, a sparse variant of the DP, and an Integer Linear Program (ILP). Evaluation of our methods on three different datasets showed that thousands of alignments can be computed in a matter of minutes using DP, even for ‘challenging’ instances. Running times of the sparse DP were an order of magnitude better than for the classical DP. The ILP was clearly outperformed by both DP approaches. We also found that for both DP algorithms, computing the 1% slowest alignments required as much time as computing the 99% fastest.Contact: sebastian.boecker@uni-jena.de [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 13674803
- Volume :
- 28
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- Bioinformatics
- Publication Type :
- Academic Journal
- Accession number :
- 76535343
- Full Text :
- https://doi.org/10.1093/bioinformatics/bts207