| 講演名 | 2006-05-24 動的近傍操作を用いたDNA塩基配列設計 川下 優, 小野 廣隆, 定兼 邦彦, 山下 雅史, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 近年,DNA塩基配列集合を利用したナノコンピューティング・ナノテクノロジーが注目されている.これらの技術に用いられる塩基配列集合は,利用目的に応じた制約を満たす必要がある.いくつかの制約は組合せ的であるので,本論文では塩基配列集合問題を組合せ最適化問題と捉える.さらに,他の制約より組合せ的なオーバーラップ指標に着目し,局所探索法に基づくアルゴリズムを提案する.このアルゴリズムでは組合せ的制約を局所探索法で充足させるために,可変近傍探索法・可変深度探索近傍法と呼ばれる動的近傍操作を採用する.計算機実験において,提案手法は同様の制約を満たす他の手法と同等以上の配列集合の設計に成功した. |
| 抄録(英) | In recent years, DNA sequence sets are used in various fields such as nanotechnology and nanocomputing. Since there are several applications using the sequence sets, the sequence sets need to satisfy several constraints depending on the applications. Since several constraints are combinatorial, we consider the sequence sets design problem where the sequence sets are used to solve combinatorial problems. For the purpose, we focus on the overlapping measure which is more combinatorial than other constraints. Then, we propose a local-search based approximation algorithm. To deal with this, we adopt a dynamic neighorhood search frame work, called Variable Neighborhood Search and Variable Depth Search. The computational experiments show that generated sequence sets are as good as the ones generated by exiting methods, or better. |
| キーワード(和) | DNA配列集合設計 / 組合せ最適化 / 局所探索法 / ハミング距離 / オーバーラップ指標 |
| キーワード(英) | DNA sequence design / Combinatorial Optimization / Local Search / Hamming distance / Overlapping measure |
| 資料番号 | COMP2006-16 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2006/5/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 動的近傍操作を用いたDNA塩基配列設計 |
| サブタイトル（和） | |
| タイトル（英） | DNA Sequence Design by Dynamic Neighborhood Searches |
| サブタイトル（和） | |
| キーワード(1)（和/英） | DNA配列集合設計 / DNA sequence design |
| キーワード(2)（和/英） | 組合せ最適化 / Combinatorial Optimization |
| キーワード(3)（和/英） | 局所探索法 / Local Search |
| キーワード(4)（和/英） | ハミング距離 / Hamming distance |
| キーワード(5)（和/英） | オーバーラップ指標 / Overlapping measure |
| 第 1 著者 氏名（和/英） | 川下 優 / Suguru KAWASHIMO |
| 第 1 著者 所属（和/英） | 九州大学 大学院 システム情報科学府 Dept. of Electrical Engineering and Computer Science, Kyushu University |
| 第 2 著者 氏名（和/英） | 小野 廣隆 / Hirotaka ONO |
| 第 2 著者 所属（和/英） | 九州大学 大学院 システム情報科学研究院 Dept. of Computer Science and Communication Engineering, Kyushu University |
| 第 3 著者 氏名（和/英） | 定兼 邦彦 / Kunihiko SADAKANE |
| 第 3 著者 所属（和/英） | 九州大学 大学院 システム情報科学研究院 Dept. of Computer Science and Communication Engineering, Kyushu University |
| 第 4 著者 氏名（和/英） | 山下 雅史 / Masafumi YAMASHITA |
| 第 4 著者 所属（和/英） | 九州大学 大学院 システム情報科学研究院 Dept. of Computer Science and Communication Engineering, Kyushu University |
| 発表年月日 | 2006-05-24 |
| 資料番号 | COMP2006-16 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 63 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |