Please use this identifier to cite or link to this item:
Title: Pattern matching and pattern discovery algorithms for protein topologies
Authors: Viksna, J
Gilbert, D
Issue Date: 2001
Publisher: Springer
Citation: Proceedings of the First International Workshop on Algorithms in BioInformatics BRICS, University of Aarhus, Denmark, 28-31 August 2001, pp. 98-111
Abstract: 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 the apparent inefficiency such approach gives 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 which 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.
ISBN: 3-540-42516-0
ISSN: 0302-9743
Appears in Collections:Computer Science
Dept of Computer Science Research Papers

Files in This Item:
File Description SizeFormat kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.