TY - GEN

T1 - A local search based barrier height estimation algorithm for DNA molecular transitions

AU - Takeda, Tsutomu

AU - Ono, Hirotaka

AU - Sadakane, Kunihiko

AU - Yamashita, Masafumi

PY - 2006

Y1 - 2006

N2 - An accurate estimation of the barrier height between two given secondary structures of DNA molecules is known to be a fundamental and difficult problem. In 1998 Morgan and Higgs proposed a heuristic algorithm based on the shortest path between the two structures, and in DNA 10, Kubota and Hagiya did an exact algorithm based on the flooding. The former runs in a practical time for sufficiently large length n of molecule and would always show a good performance if the barrier always appeared near the shortest path. The only but crucial drawback of the latter on the other hand is that it cannot run for a large n; we found an instance of even length n = 46 for which the run did not complete because of the memory. In this paper we formulate it as an optimization problem, and then propose a new heuristic algorithm based on the local search strategy. We use the Morgan and Higgs' heuristics as the engine to und a locally optimal solution, and based on the local search paradigm, we repeat this local search starting from the solution of the previous local search, with the hope that this sequence of improvements will eventually reach the optimum solution. We also discuss some techniques to improve the performance. We demonstrate that for size about 200, our algorithm runs in 5 seconds, and for many of the cases (13 cases out of 16) in which the Kubota and Hagiya's algorithm can complete, our algorithm exactly answers the optimum values.

AB - An accurate estimation of the barrier height between two given secondary structures of DNA molecules is known to be a fundamental and difficult problem. In 1998 Morgan and Higgs proposed a heuristic algorithm based on the shortest path between the two structures, and in DNA 10, Kubota and Hagiya did an exact algorithm based on the flooding. The former runs in a practical time for sufficiently large length n of molecule and would always show a good performance if the barrier always appeared near the shortest path. The only but crucial drawback of the latter on the other hand is that it cannot run for a large n; we found an instance of even length n = 46 for which the run did not complete because of the memory. In this paper we formulate it as an optimization problem, and then propose a new heuristic algorithm based on the local search strategy. We use the Morgan and Higgs' heuristics as the engine to und a locally optimal solution, and based on the local search paradigm, we repeat this local search starting from the solution of the previous local search, with the hope that this sequence of improvements will eventually reach the optimum solution. We also discuss some techniques to improve the performance. We demonstrate that for size about 200, our algorithm runs in 5 seconds, and for many of the cases (13 cases out of 16) in which the Kubota and Hagiya's algorithm can complete, our algorithm exactly answers the optimum values.

UR - http://www.scopus.com/inward/record.url?scp=33745740792&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745740792&partnerID=8YFLogxK

U2 - 10.1007/11753681_28

DO - 10.1007/11753681_28

M3 - Conference contribution

AN - SCOPUS:33745740792

SN - 3540341617

SN - 9783540341611

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 359

EP - 370

BT - DNA Computing - 11th International Workshop on DNA Computing, DNA11, Revised Selected Papers

T2 - 11th International Workshop on DNA Computing, DNA11

Y2 - 6 June 2005 through 9 June 2005

ER -