Finding all maximal common substructures in proteins

Abstract

Finding the common substructures shared by two proteins is considered as one ofthe central issues in computational biology due to its usefulness in understandingstructure-function relationship and application in drug and vaccine design. Unlikethe structural alignment problem, a good solution for the common substructureidentification problem should produce results that include:1. All possible common substructures (CS),2. CSs whose elements do not follow the same backbone order,3. CSs spanning multiple polypeptide chains,4. Ranking mechanism so that potentially biologically interesting structure ison the top.We propose a novel algorithm called FAMCS (Finding All Maximal CommonSubstructures). Experiments on various proteins show that FAMCS can addressall four requirements and infer interesting biological discoveries.