Paper Info
Title
Study of Protein Structure Alignment Problem in Parameterized Computation.
Abstract
Motivated by the practical application of protein structure-structure alignment, we have studied the problem of maximum common subgraph within the framework of parameterized complexity. We investigated the lower bound for the exact algorithms of the problem. We proved it unlikely that there is an algorithm of time p(n,m) * k(o(m)) for the problem, where p is a polynomial function, k is a parameter of map width, and m and n are the numbers of vertices of the the two graphs respectively. In consideration of the upper bound of p(n,m)*k(m) based on the brute-force approach, our lower bound result is asymptotically tight. Although the algorithm with the running time p(n,m) k(m) could not be significantly improved from our lower bound result, it is still possible to develop efficient algorithms or the practical application of the protein structure-structure alignment. We developed an efficient algorithm integrating the color coding method and parameterized computation for identifying the maximum common subgraph of two prot structure graphs. We have applied the algorithm to protein structure-structure alignment and conducted experimental testing of more than 600 protein pairs. Our parameterized approach shows improvement in structure alignment efficiency and will be very useful for structure comparisons of proteins with large sizes.
Year
DOI
Venue
2012
10.5220/0003769701740181
BIOINFORMATICS: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON BIOINFORMATICS MODELS, METHODS AND ALGORITHMS
Keywords
Field
DocType
Protein structure-structure alignment,Color coding,Parameterized computation,Maximum common subgraph
Computer science,Theoretical computer science,Parameterized computation,Protein structure
Conference
Citations 
PageRank 
References 
0
0.34
0
Authors
4
Name
Order
Citations
PageRank
Cody Ashby121.40
Kun Wang200.34
Carole L Cramer321.74
Xiuzhen Huang444226.16