Identification of the possible chemical constituents in a mixture solution from LC-MS analysis is an important task and can be reduced as a combinatorial problem. There are two given inputs in the problem. One is a scaffold of a known chemical constituent in a mixture and another is a list of side chain groups that can be substituted on the scaffold. Each side chain has a probability from the distribution of natural products database. The problem is defined as how to generate the possible structures by extending the side chain groups to the given scaffold satisfying both two conditions: re-assembled structures have the equal molecular weights with a target weight corresponding to the peak table from LC-MAS spectra and have the highest probability that is a product of all probabilities of substituent. The defined combinatorial problem was proven as NP-hard. We proposed a pseudo-polynomial time algorithm based on dynamic programming strategy to efficiently identify the possible constituents. Furthermore, the method can search the optimal solutions.

Efficient dynamic programming algorithm to predict novel chemical structures in a mixture

243rd National Meeting (2012)

The official archive and repository for all ACS Meetings & Expositions abstracts and select posters or presentations.