6533b7d3fe1ef96bd126094a

RESEARCH PRODUCT

Pattern Matching and Pattern Discovery Algorithms for Protein Topologies

Juris ViksnaDavid Gilbert

subject

CombinatoricsDiscrete mathematicsSubgraph isomorphism problemMaximal independent setInduced subgraph isomorphism problemPattern matchingFast methodsNetwork topologyTime complexityAlgorithmMaximum common subgraph isomorphism problemMathematicsofComputing_DISCRETEMATHEMATICSMathematics

description

We describe algorithms for pattern-matching and pattern-learning in TOPS diagrams (formal descriptions of protein topologies). These problems can be reduced to checking for subgraph isomorphism and finding maximal common subgraphs in a restricted class of ordered graphs. We have developed a subgraph isomorphism algorithm for ordered graphs, which performs well on the given set of data. The maximal common subgraph problem then is solved by repeated subgraph extension and checking for isomorphisms. Despite its apparent inefficiency, this approach yields an algorithm with time complexity proportional to the number of graphs in the input set and is still practical on the given set of data. As a result we obtain fast methods that can be used for building a database of protein topological motifs and for the comparison of a given protein of known secondary structure against a motif database.

yearjournalcountryeditionlanguage
2001-01-01
https://doi.org/10.1007/3-540-44696-6_8