Email this article 
Open Access
Subscription or Fee Access
An Improved Branch and Bound Algorithm for Cyclopeptide Sequencing
Abstract
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.
Keywords
References
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. https://beta.stepic.org/Bioinformatics-Algorithms-2/Sequencing-Antibiotics-by-Shattering-Them-into-Pieces-98/
Phillip Compeau and Pavel Pevzner. (2013). Bioinformatics Algorithms https://beta.stepic.org/Bioinformatics-Algorithms-2/Adapting-Cyclopeptide-Sequencing-for-Spectra-with-Errors-102/#step-1
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
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.