We used a divide-and-conquer algorithm to recursively solve the two-dimensional problem of protein folding of an HP sequence with the maximum number of H-H contacts. We derived both lower and upper bounds for the algorithmic complexity by using the newly introduced concept of multi-directional width-bounded geometric separator. We proved that for a grid graph G with n grid points P, there exists a balanced separator A subseteq P$ such that A has less than or equal to 1.02074 sqrt{n} points, and G-A has two disconnected subgraphs with less than or equal to {2over 3}n nodes on each subgraph. We also derive a 0.7555sqrt {n} lower bound for our balanced separator. Based on our multidirectional width-bounded geometric separator, we found that there is an O(n^{5.563sqrt{n}}) time algorithm for the 2D protein folding problem in the HP model. We also extended the upper bound results to rectangular and triangular lattices.
| Identifer | oai:union.ndltd.org:uno.edu/oai:scholarworks.uno.edu:td-1242 |
| Date | 20 May 2005 |
| Creators | Oprisan, Sorinel |
| Publisher | ScholarWorks@UNO |
| Source Sets | University of New Orleans |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | University of New Orleans Theses and Dissertations |
Page generated in 0.002 seconds