No Access

MULTI-DIRECTIONAL WIDTH-BOUNDED GEOMETRIC SEPARATOR AND PROTEIN FOLDING

BIN FU

Department of Computer Science, University of Texas-Pan American, Edinburg, TX 78539, USA

Search for more papers by this author

SORINEL A. OPRISAN

Department of Physics and Astronomy, College of Charleston, Harleston, SC 29424, USA

Search for more papers by this author

, and

LIZHE XU

US DHS PIADC, 40550 Route 25, Orient Point, NY 11957, USA

Search for more papers by this author

https://doi.org/10.1142/S0218195908002696Cited by:2 (Source: Crossref)

Abstract

We introduce the concept of multi-directional width-bounded geometric separators and obtain an improved separator for grid graphs. This yields an improved exact algorithm for the protein folding problem in the HP-model. For a grid graph G with n grid points P, there exists a separator A ⊆ P such that A has at most points, and G − A has two disconnected subgraphs each with at most nodes. This improves the previous upper bound of . We also derive a lower bound for such a separator in grid graphs.

This research is supported by Louisiana Board of Regents fund under contract number LEQSF(2004-07)-RD-A-35. Part of the research was done when Bin Fu and Lizhe Xu were associated with the Department of Computer Science, University of New Orleans, New Orleans, LA 70148 and Research Institute for Children, 200 Henry Clay Avenue, New Orleans, LA 70118, and when Sorinel A Oprisan was associated with the Department of Psychology, University of New Orleans, New Orleans, LA 70148.

Keywords:

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

References

N. Alon, P. Seymour and R. Thomas, SIAM J. Discr. Math. 7(2), 184 (1990), DOI: 10.1137/S0895480191198768. Crossref, Web of Science, Google Scholar
N. Alon, P. Seymour and R. Thomas, A separator theorem for graphs with an excluded minor and its applications, Proc. 22nd ACM Symp. Theory of Computing (1990) pp. 293–299. Google Scholar
B. Berger and T. Leighton, J. Comput. Biol. 5, 27 (1998), DOI: 10.1089/cmb.1998.5.27. Crossref, Web of Science, Google Scholar
S. N. Bhatt and F. T. Leighton, J. Comput. Syst. Sci. 28(2), 300 (1982), DOI: 10.1016/0022-0000(84)90071-0. Crossref, Web of Science, Google Scholar
N. Chiba, T. Nishizeki and T. Saito, Inform. Process. Lett. 4(4), 203 (1981). Google Scholar
P. Crescenziet al., J. Comput. Biol. 5, 423 (1998), DOI: 10.1089/cmb.1998.5.423. Crossref, Web of Science, Google Scholar
A. Dessmark, A. Lingas and E.-M. Lundell, Subexponential-time framework for optimal embeddings of graphs in integer lattices, Proc. 9th Scandinavian Workshop on Algorithm Theory3111, Lecture Notes in Computer Science pp. 248–259. Google Scholar
H. N. Djidjev, SIAM J. Discr. Math. 3(2), 229 (1982). Crossref, Web of Science, Google Scholar
H. N. Djidjev and S. M. Venkatesan, Acta Informatica 34, 231 (1997), DOI: 10.1007/s002360050082. Crossref, Web of Science, Google Scholar
B. Fu and W. Wang, A 2O (n1–1/d log n)-time algorithm for d-dimensional protein folding in the HP-model, Proc. 31st Int. Colloquium on Automata, Languages and Programming (2004) pp. 630–644. Google Scholar
B. Fu, Theory and application of width bounded geometric separator, Proc. 23rd Ann. Symp. Theoretical Computer Science3884, Lecture Notes in Computer Science (2005) pp. 278–288. Google Scholar
H. Gazit, An improved algorithm for separating a planar graph, manuscript, USC, 1986 . Google Scholar
J. R. Gilbert, J. P. Hutchinson and R. E. Tarjan, J. Algorith. 5, 391 (1984), DOI: 10.1016/0196-6774(84)90019-1. Crossref, Web of Science, Google Scholar
K. F. Lau and K. A. Dill, Macromolecules 22, 3986 (1989), DOI: 10.1021/ma00200a030. Crossref, Web of Science, Google Scholar
K. F. Lau and K. A. Dill, Proc. Nat. Acad. Sci. 87, 638 (1990), DOI: 10.1073/pnas.87.2.638. Crossref, Web of Science, Google Scholar
R. J. Lipton and R. Tarjan, SIAM J. Appl. Math. 36, 177 (1979), DOI: 10.1137/0136016. Crossref, Web of Science, Google Scholar
R. J. Lipton and R. Tarjan, SIAM J. Comput. 9(3), 615 (1980), DOI: 10.1137/0209046. Crossref, Web of Science, Google Scholar
G. L. Miller, S.-H. Teng and S. A. Vavasis, A unified geometric approach to graph separators, Proc. 32nd IEEE Symp. Foundations of Computer Science (1991) pp. 538–547. Google Scholar
G. L. Miller and W. Thurston, Separators in two and three dimensions, Proc. 22nd ACM Symp. Theory of Computing (1990) pp. 300–309. Google Scholar
G. L. Miller and S. A. Vavasis, Density graphs and separators, Proc. 2nd ACM-SIAM Symp. Discrete Algorithms (1991) pp. 331–336. Google Scholar
S. Plotkin, S. Rao and W. D. Smith, Shallow excluded minors and improved graph decomposition, Proc. 5th ACM-SIAM Symp. Discrete Algorithms (1990) pp. 462–470. Google Scholar
S. S. Ravi and H. B. Hunt III, Inform. Process. Lett. 25(5), 317 (1987), DOI: 10.1016/0020-0190(87)90206-7. Crossref, Web of Science, Google Scholar
W. D. Smith and N. C. Wormald, Application of geometric separator theorems, Proc. 39th IEEE Symp. Foundations of Computer Science (1998) pp. 232–243. Google Scholar
D. A. Spielman and S. H. Teng, Disk packings and planar separators, Proc. 12th ACM Symp. Computational Geometry (1996) pp. 349–358. Google Scholar
J. Pach and P. K. Agarwal , Combinatorial Geometry ( Wiley-Interscience Publication , 1995 ) . Crossref, Google Scholar
R. Weinstock , Calculus of Variations ( McGraw-Hill , 1952 ) . Google Scholar
W. Smith, personal communication, 2005 . Google Scholar