An Improved Branch and Bound Algorithm for Cyclopeptide Sequencing

The mass-production of antibiotics and medication has started an evolutionary race between antibiotics and bacteria. Pharmaceutical companies proved helpful to create new antibiotics, while pathogens developed a new level of resistance to these antibiotics. Growth of drug-resistant disease increases the challenge of searching for new, more effective antibiotics. The isolation and sequencing of cyclic peptide antibiotics is time-consuming and error-prone, compared with the linear peptides. Given these facts, there is a need for new tools to sequence cyclic non-ribosomal proteins (NRPs). In this paper we show how to improve the cyclic peptide sequencing method further to reduce its running time considerably in its expansion (branching) step. Our results suggest that instead of extending the k-mers over the full span of 18 to more than 100 amino acids, we could extend the k-mers just over the candidate amino acids measured in the first step of the cyclic peptide sequencing method. This strategy improves the running time and space requirement of the method significantly.