A Multi-Dimensional Width-Bounded Geometric Separator and its Applications to Protein Folding

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Year

2005

Author dc:creator

• Oprisan, Sorinel

Contributors dc:contributor

• Fu, Bin
• DePano, Adlai
• Chen, Yixin

• Planar graphs
• Divide and conquer
• HP model
• Algorithmic complexity
• Grid graphs

Repository record dc:identifier

https://scholarworks.uno.edu/td/238

OAI identifier oai:identifier

oai:scholarworks.uno.edu:td-1242