A simple and fast heuristic for protein structure comparison
MetadatosMostrar el registro completo del ítem
AlgorithmsAmino acid sequenceMolecular sequence dataPatter recognitionProtein conformationProteinsSequence analysisSoftware
Pelta, D.A.; González, J.R.; Moreno Vega, M. A simple and fast heuristic for protein structure comparison. BMC Bioinformatics, 9: 161 (2008). [http://hdl.handle.net/10481/31182]
PatrocinadorThis work is supported by Projects HeuriCosc TIN2005-08404-C04-01, HeuriCode TIN2005-08404-C04-03, both from the Spanish Ministry of Education and Science. JRG acknowledges financial support from Project TIC2002-04242-C03-02. Authors thank N. Krasnogor and ProCKSi project (BB/C511764/1) for their support.
Background Protein structure comparison is a key problem in bioinformatics. There exist several methods for doing protein comparison, being the solution of the Maximum Contact Map Overlap problem (MAX-CMO) one of the alternatives available. Although this problem may be solved using exact algorithms, researchers require approximate algorithms that obtain good quality solutions using less computational resources than the formers. Results We propose a variable neighborhood search metaheuristic for solving MAX-CMO. We analyze this strategy in two aspects: 1) from an optimization point of view the strategy is tested on two different datasets, obtaining an error of 3.5%(over 2702 pairs) and 1.7% (over 161 pairs) with respect to optimal values; thus leading to high accurate solutions in a simpler and less expensive way than exact algorithms; 2) in terms of protein structure classification, we conduct experiments on three datasets and show that is feasible to detect structural similarities at SCOP's family and CATH's architecture levels using normalized overlap values. Some limitations and the role of normalization are outlined for doing classification at SCOP's fold level. Conclusion We designed, implemented and tested.a new tool for solving MAX-CMO, based on a well-known metaheuristic technique. The good balance between solution's quality and computational effort makes it a valuable tool. Moreover, to the best of our knowledge, this is the first time the MAX-CMO measure is tested at SCOP's fold and CATH's architecture levels with encouraging results. Software is available for download at http://modo.ugr.es/jrgonzalez/msvns4maxcmo webcite.