WEKO3
アイテム
効率的クリークアルゴリズムに基づく電気泳動画像マッチング、タンパク質構造マッチング、および、タンパク質側鎖パッキング
https://ipsj.ixsq.nii.ac.jp/records/33440
https://ipsj.ixsq.nii.ac.jp/records/3344049c19c53-9abe-4439-ba5d-aaee2871d5c1
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-MPS02039006.pdf (81.3 kB)
|
Copyright (c) 2002 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2002-05-10 | |||||||
| タイトル | ||||||||
| タイトル | 効率的クリークアルゴリズムに基づく電気泳動画像マッチング、タンパク質構造マッチング、および、タンパク質側鎖パッキング | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Point matching under non - uniform distortions and protein side chain packing based on efficient maximum clique algorithms | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 京都大学化学研究所バイオインフォマティクスセンター／京都大学大学院情報学研究科知能情報学専攻 | ||||||||
| 著者所属 | ||||||||
| 京都大学化学研究所バイオインフォマティクスセンター／京都大学大学院情報学研究科知能情報学専攻 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学大学院電気通信学研究科電子情報学専攻 | ||||||||
| 著者所属 | ||||||||
| 電気通信大学大学院電気通信学研究科電子情報学専攻 | ||||||||
| 著者所属 | ||||||||
| 国立情報学研究所 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Bioinformatics Center, Institute for Chenmical Research, Kyoto University/Graduate School of Informatics, Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Bioinformatics Center, Institute for Chenmical Research, Kyoto University/Graduate School of Informatics, Kyoto University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Electro - Communications, The University of Electro - Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Graduate School of Electro - Communications, The University of Electro - Communications | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| National Institute of Informatics | ||||||||
| 著者名 |
ケーシードゥッカバハドゥル
× ケーシードゥッカバハドゥル
|
|||||||
| 著者名(英) |
Dukka, BahadurK.C.
× Dukka, BahadurK.C.
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 電気泳動画像マッチング、タンパク質構造マッチング、タンパク質側鎖パッキングはいずれもバイオインフォマティクスにおいて有用なNP困難問題である。これらの問題に対して効率的な最大クリークアルゴリズムを用いた一連のアルゴリズムを開発し、計算機実験によりその性能を検証した。その結果、直接クリーク問題に変換するアルゴリズムを用いた場合は、50残基（点）から150残基（点）からなる入力に対して１CPUで最適解を現実的な時間で計算することができた。また、いくつかのヒューリスティクスを組み合わせることにより、より現実的なサイズの問題に対して、良好な解を得ることができた。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We developed maximum clique-based algorithms for spot matching for two-dimensional gel electrophoresis images, protein structure alignment and protein side-chain packing, where these problems are known to be NP-hard. Algorithms based on direct reductions to the maximum clique can find optimal solutions for instances of size (the number of points or residues) up to 50$\sim$150 using a standard PC. We developed pre-processing techniques to reduce the size of graphs. Combined with some heuristics, many realistic instances can be solved approximately. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10505667 | |||||||
| 書誌情報 |
情報処理学会研究報告数理モデル化と問題解決（MPS） 巻 2002, 号 36(2002-MPS-039), p. 21-24, 発行日 2002-05-10 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
