ダウンロード数: 256
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
cmb.2012.0133.pdf | 433.76 kB | Adobe PDF | 見る/開く |
タイトル: | A clique-based method using dynamic programming for computing edit distance between unordered trees. |
著者: | Mori, Tomoya https://orcid.org/0000-0003-3483-0056 (unconfirmed) Tamura, Takeyuki https://orcid.org/0000-0003-1596-901X (unconfirmed) Fukagawa, Daiji Takasu, Atsuhiro Tomita, Etsuji Akutsu, Tatsuya https://orcid.org/0000-0001-9763-797X (unconfirmed) |
著者名の別形: | 阿久津, 達也 |
発行日: | Oct-2012 |
出版者: | Mary Ann Liebert, Inc. |
誌名: | Journal of computational biology |
巻: | 19 |
号: | 10 |
開始ページ: | 1089 |
終了ページ: | 1104 |
抄録: | Abstract Many kinds of tree-structured data, such as RNA secondary structures, have become available due to the progress of techniques in the field of molecular biology. To analyze the tree-structured data, various measures for computing the similarity between them have been developed and applied. Among them, tree edit distance is one of the most widely used measures. However, the tree edit distance problem for unordered trees is NP-hard. Therefore, it is required to develop efficient algorithms for the problem. Recently, a practical method called clique-based algorithm has been proposed, but it is not fast for large trees. This article presents an improved clique-based method for the tree edit distance problem for unordered trees. The improved method is obtained by introducing a dynamic programming scheme and heuristic techniques to the previous clique-based method. To evaluate the efficiency of the improved method, we applied the method to comparison of real tree structured data such as glycan structures. For large tree-structures, the improved method is much faster than the previous method. In particular, for hard instances, the improved method achieved more than 100 times speed-up. |
著作権等: | This is a copy of an article published in the Journal of computational biology. ©2012 Mary Ann Liebert, Inc. publishers. "Journal of computational biology" is available online at: http://online.liebertpub.com. This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 |
URI: | http://hdl.handle.net/2433/160699 |
DOI(出版社版): | 10.1089/cmb.2012.0133 |
PubMed ID: | 23057820 |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。