Publication Type:

Conference Paper

Source:

Proceedings of the International Symposium on Biocomputing, ACM (2010)

URL:

http://dl.acm.org/citation.cfm?id=1722047

Abstract:

The search of structural motifs that specify the spatial arrangement of polypeptide segments is preferred over other methods such as common substructure discovery and structural superposition in comparing protein structures. 3D protein structures can be modeled as graphs whose maximum degree is bounded by a constant. Structural motifs can also be modeled as graphs and a significant percentage of them are trees. Thus, motif search in proteins can be modeled as an enumeration of isomorphic subgraphs where a query tree Q with m nodes is searched in a sparse graph G with n nodes and the maximum degree of any node in G is bounded by a constant ε. We design an efficient divide-and-conquer algorithm that finds all copies of Q in G by partitioning Q using a minimum dominating set. This strategy can be extended to sparse query graphs that can be reduced to trees by deleting a small number of edges.

Cite this Research Publication

Dr. Bhadrachalam Chitturi, Bein, D., and Grishin, N. V., “Complete enumeration of compact structural motifs in proteins”, in Proceedings of the International Symposium on Biocomputing, 2010.

207
PROGRAMS
OFFERED
6
AMRITA
CAMPUSES
15
CONSTITUENT
SCHOOLS
A
GRADE BY
NAAC, MHRD
8th
RANK(INDIA):
NIRF 2018
150+
INTERNATIONAL
PARTNERS