Open Access Open Access  Restricted Access Subscription or Fee Access

An Improved Branch and Bound Algorithm for Cyclopeptide Sequencing

Sangharsh Saini, Monika Saini


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.


Algorithms, Amino Acids, Antibiotics, Cyclopeptide Sequencing, Spectral Convolution.

Full Text:



Dirk Schwarzer, Robert Finking, and Mohamed A. Marahiel (2003). "Nonribosomal peptides: from genes to products". Nat. Prod. Rep. 20 (3): 275–87. doi:10.1039/b111145k. PMID 12828367

Robert K. Boyd (1994). "Linked-scan techniques for MS/MS using tandem-in-space instruments". Mass Spectrometry Reviews 13 (5–6): 359–410. doi:10.1002/mas.1280130502

Pevzner, P., "Keynote: De novo sequencing of novel peptide antibiotics by tandem mass spectrometry," Computational Advances in Bio and Medical Sciences (ICCABS), 2012 IEEE 2nd International Conference on , vol., no., pp.1,1, 23-25 Feb. 2012

Phillip Compeau and Pavel Pevzner. (2013). Bioinformatics Algorithms.

Phillip Compeau and Pavel Pevzner. (2013). Bioinformatics Algorithms

Hwang, J.S.; Park, S.W.; Cho, J.B.; Oh, K. S.; Yang, S.S.; Lee, Soonil; Koh, K.H.; Jung, K.W., "The Micro Mass Spectrometer with A Carbon Nano Structure Ion Source," Nano/Micro Engineered and Molecular Systems, 2006. NEMS '06. 1st IEEE International Conference on , vol., no., pp.1220,1223, 18-21 Jan. 2006

Wapelhorst, E.; Hauschild, J.-P.; Müller, J., "A One - Chip Solution of a Mass Spectrometer," Solid-State Sensors, Actuators and Microsystems Conference, 2007. TRANSDUCERS 2007. International , vol., no., pp.2015,2018, 10-14 June 2007

Ainbinder, I.; Pinto, G.; Rabinowitz, Gad; Ben-Dov, Y.T., "A Customized Branch and Bound Algorithm to Solve the Resource-Sharing and Scheduling Problem (RSSP)," Computational Cybernetics, 2006. ICCC 2006. IEEE International Conference on , vol., no., pp.1,5, 20-22 Aug. 2006

Chang, Robin L P; Pavlidis, Theodosios, "Fuzzy Decision Tree Algorithms," Systems, Man and Cybernetics, IEEE Transactions on , vol.7, no.1, pp.28,35, Jan. 1977

Chuang LY, Chang HW, Lin MC, Yang CH. Improved branch and bound algorithm for detecting SNP-SNP interactions in breast cancer. J Clin Bioinforma. 2013 Feb 4;3(1):4. doi: 10.1186/2043-9113-3-4. PubMed PMID: 23410245; PubMed Central PMCID: PMC3626712.

Brusco MJ. An enhanced branch-and-bound algorithm for a partitioning problem. Br J Math Stat Psychol. 2003 May;56(Pt 1):83-92. PubMed PMID: 12803823.

Nicola Cannata, Stefano Toppo, Chiara Romualdi, and Giorgio Valle “Simplifying amino acid alphabets by means of a branch and bound algorithm and substitution matrices” Bioinformatics (2002) 18 (8): 1102-1108 doi:10.1093/bioinformatics/18.8.1102


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.