An efficient computer-aided structural elucidation strategy for mixtures using an iterative dynamic programming algorithm
Bo-Han Su, Mengyu Shen, Yeu‐Chern Harn et al. · Journal of Cheminformatics · 2017
The identification of chemical structures in natural product mixtures is an important task in drug discovery but is still a challenging problem, as structural elucidation is a time-consuming process and is limited by the available mass spectra of known natural products. Computer-aided structure elucidation (CASE) strategies seek to automatically propose a list of possible chemical structures in mixtures by utilizing chromatographic and spectroscopic methods. However, current CASE tools still cannot automatically solve structures for experienced natural product chemists. Here, we formulated the structural elucidation of natural products in a mixture as a computational problem by extending a list of scaffolds using a weighted side chain list after analyzing a collection of 243,130 natural products and designed an efficient algorithm to precisely identify the chemical structures. The complexity of such a problem is NP-complete. A dynamic programming (DP) algorithm can solve this NP-complete problem in pseudo-polynomial time after converting floating point molecular weights into integers. However, the running time of the DP algorithm degrades exponentially as the precision of the mass spectrometry experiment grows. To ideally solve in polynomial time, we proposed a novel iterative DP algorithm that can quickly recognize the chemical structures of natural products. By utilizing this algorithm to elucidate the structures of four natural products that were experimentally and structurally determined, the algorithm can search the exact solutions, and the time performance was shown to be in polynomial time for average cases. The proposed method improved the speed of the structural elucidation of natural products and helped broaden the spectrum of available compounds that could be applied as new drug candidates. A web service built for structural elucidation studies is freely accessible via the following link ( http://csccp.cmdm.tw/ ).
Cited by 4 works. doi:10.1186/s13321-017-0244-9 Open-access PDF
Authors
- Bo-Han Su
- Mengyu Shen
- Yeu‐Chern Harn
- San‐Yuan Wang
- Alioune Schurz
- Chieh Lin
- Olivia A. Lin
- Yufeng Jane Tseng
References
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Natural Products as Sources of New Drugs over the Last 25 Years
- XCMS: Processing Mass Spectrometry Data for Metabolite Profiling Using Nonlinear Peak Alignment, Matching, and Identification
- ZINC − A Free Database of Commercially Available Compounds for Virtual Screening
- The evolving role of natural products in drug discovery
- Natural products: A continuing source of novel drug leads
- The Role of Natural Product Chemistry in Drug Discovery
- Applications of artificial intelligence for chemical inference. I. Number of possible organic compounds. Acyclic structures containing carbon, hydrogen, oxygen, and nitrogen
- Structure elucidation of the antibiotic desertomycin through the use of new two-dimensional NMR techniques
- Advances in structure elucidation of small molecules using mass spectrometry