Algorithms for Chemical Space Enumeration and Applications in Astrobiology

Abstract

From its very beginnings the development of algorithms for the enumeration of chemical space was closely related to NASA's early exobiology activities. The complete and non-redundant generation of all connectivity isomers corresponding to a given molecular formula was part of the DENDRAL program, established in the mid-1960s. In the 1970s mathematicians provided new techniques to increase efficiency of the first approaches, and starting with the 1990s implementations became available as software packages for customary computers. In this talk some of the most essential principles of exhaustive and non-redundant structure enumeration are reviewed: starting from simple labeled graphs we will see how to avoid isomorphic duplicates, introduce structural constraints and how to generate molecular graphs in an efficient way. Recently these methods have been rediscovered for application in astrobiology and origins of life research, particularly for generating and analyzing virtual chemical compound libraries surrounding the most important biomolecules. Results concerning the genetically encoded amino acid alphabet, nucleotide analogs and the core of intermediary metabolism are summarized.