Parallel formula generator based on branch-and-bound algorithm for elucidating high resolution mass spectra

The identification of unknown molecules by mass spectrometry is one of the most challenging problems despite the development of the instrument. One of the crucial steps is to obtain the possible elemental compositions within the limit of the measurement of mass-to-charge ratio and the mass tolerance. However, as the number of possible elements and the molecular weight increase, the more calculation time is needed. Here, a formula generator based on template metaprogramming and parallel computing is proposed to generate the possible candidate formulas. The template metaprogramming has been applied to replace the inefficient recursion to create the nested loops at compile-time for enumerating the possible elements. To accelerate the computation speed, the branch-and-bound algorithm is used to constrain the number of loop for each element. The parallel computing procedure is based on the Open Multi-Processing (OpenMP). The calculation time for calculating the candidates in the mass ranges especially for the higher ones can be significantly reduced when comparing with the popular HR2 program. PFG is implemented in C ++ and available at https://github.com/zmzhang/PFG. It can be compiled easily and run smoothly in both Windows and Linux.