TY - GEN
T1 - Speeding up local-search type algorithms for designing DNA sequences under thermodynamical constraints
AU - Kawashimo, Suguru
AU - Kaow Ng, Yen
AU - Ono, Hirotaka
AU - Sadakane, Kunihiko
AU - Yamashita, Masafumi
N1 - Funding Information:
This research partly received financial support from Scientific Research Fund of Ministry of Education, Culture, Sports, Science and Technology (KAKENHI).
PY - 2009
Y1 - 2009
N2 - We present general techniques to speed up local search type algorithms for designing DNA sequences which satisfy thermodynamical constraints based on the minimum free energy (MFE) criteria. MFE based constraints are generally difficult to handle in local search type algorithms, since these algorithms typically require a large number of time-consuming calculations of MFE to find an improved solution. In this paper, we introduce general techniques to reduce such calculations of MFE. The ideas are based on the reuse of MFE computations and fast approximation of MFE, both of which fit the nature of local search type algorithms. In computational experiments, our techniques succeeded in speeding up typical local search type algorithms without degenerating the original performance of the algorithms.
AB - We present general techniques to speed up local search type algorithms for designing DNA sequences which satisfy thermodynamical constraints based on the minimum free energy (MFE) criteria. MFE based constraints are generally difficult to handle in local search type algorithms, since these algorithms typically require a large number of time-consuming calculations of MFE to find an improved solution. In this paper, we introduce general techniques to reduce such calculations of MFE. The ideas are based on the reuse of MFE computations and fast approximation of MFE, both of which fit the nature of local search type algorithms. In computational experiments, our techniques succeeded in speeding up typical local search type algorithms without degenerating the original performance of the algorithms.
UR - http://www.scopus.com/inward/record.url?scp=70450205753&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70450205753&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03076-5_14
DO - 10.1007/978-3-642-03076-5_14
M3 - Conference contribution
AN - SCOPUS:70450205753
SN - 3642030750
SN - 9783642030758
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 168
EP - 178
BT - DNA Computing - 14th International Meeting on DNA Computing, DNA14, Revised Selected Papers
T2 - 14th International Meeting on DNA Computing, DNA14
Y2 - 2 June 2008 through 9 June 2008
ER -