| 講演名 | 2000/5/4 DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム 阿久津 達也, 金家 京徹, 大山 彰, 藤山 秋佐夫, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | DNAやタンパク質の2次元電気泳動画像を比較することは、遺伝子の異常の検出などに有効である。そのためには歪みが不均一な場合の2次元平面上の点集合パターンマッチングを行なう必要がある。本稿では、まず、不均一な歪みを持つ場合の点集合のパターンマッチング問題の形式的定義を与え、この問題が2次元以上においてNP困難であることを示す。一方、1次元でかつ点の順序が保存されるという制約つきの場合に対しての、動的計画法に基づく多項式時間アルゴリズムを示す。そして、このアルゴリズムに基づき開発した、DNA2次元電気泳動画像のパターンマッチングのためのヒューリスティック・アルゴリズムを、実行結果例とともに示す。 |
| 抄録(英) | In this paper, we study pattern matching of points under non-uniform distortions, which arises from analysis of two-dimensional (2-D) electrophoresis images. First we give a formal definition for the problem. Next we prove that it is NP-hard in two (or more) dimensions, and we present a simple polynomial time algorithm for a special and one-dimensional case of the problem. Then we present a practical heuristic algorithm for finding a matching between two sets of spots in two-dimensional gel electrophoresis images obtained from genomic DNA. Experimental results using real image data are shown too. |
| キーワード(和) | パターンマッチング / 電気泳動 / NP困難 / 点集合 / 動的計画法 |
| キーワード(英) | point matching / electrophoresis / NP-hard / dynamic programming |
| 資料番号 | PRMU2000-10, MI2000-10 |
| 発行日 |
| 研究会情報 | |
| 研究会 | MI |
|---|---|
| 開催期間 | 2000/5/4(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Medical Imaging (MI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | DNA2次元電気泳動画像のパターンマッチング : 問題の困難さとヒューリスティック・アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Matching of Spots in Two Dimensional Electrophoresis Images : Point Matching Under Non-uniform Distortion |
| サブタイトル（和） | |
| キーワード(1)（和/英） | パターンマッチング / point matching |
| キーワード(2)（和/英） | 電気泳動 / electrophoresis |
| キーワード(3)（和/英） | NP困難 / NP-hard |
| キーワード(4)（和/英） | 点集合 / dynamic programming |
| キーワード(5)（和/英） | 動的計画法 |
| 第 1 著者 氏名（和/英） | 阿久津 達也 / Tatsuya Akutsu |
| 第 1 著者 所属（和/英） | 東京大学 医科学研究所 ヒトゲノム解析センター Human Genome Center, Institute of Medical Science, University of Tokyo |
| 第 2 著者 氏名（和/英） | 金家 京徹 / Kyotetsu Kanaya |
| 第 2 著者 所属（和/英） | 三井情報開発株式会社 バイオシステム室 Department of Bioscience Systems, Mitsui Knowledge Industry Co., Ltd. |
| 第 3 著者 氏名（和/英） | 大山 彰 / Akira Ohyama |
| 第 3 著者 所属（和/英） | 三井情報開発株式会社 バイオシステム室 Department of Bioscience Systems, Mitsui Knowledge Industry Co., Ltd. |
| 第 4 著者 氏名（和/英） | 藤山 秋佐夫 / Asao Fujiyama |
| 第 4 著者 所属（和/英） | 国立遺伝学研究所 National Institute of Genetics |
| 発表年月日 | 2000/5/4 |
| 資料番号 | PRMU2000-10, MI2000-10 |
| 巻番号（vol） | vol.100 |
| 号番号（no） | 45 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |