文献

J-GLOBAL ID：201902259642322729   整理番号：19A0488653

ツリー上の代数動的計画法【JST・京大機械翻訳】

Algebraic Dynamic Programming on Trees

著者 (10件)： Berkemer Sarah J. (Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, University Leipzig, Haertelstrasse 16-18, D-04107 Leipzig, Germany) ,  Berkemer Sarah J. (Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, D-04103 Leipzig, Germany) ,  Siederdissen Christian Honer zu (Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, University Leipzig, Haertelstrasse 16-18, D-04107 Leipzig, Germany) ,  Stadler Peter F. (Bioinformatics Group, Department of Computer Science, Interdisciplinary Center for Bioinformatics, University Leipzig, Haertelstrasse 16-18, D-04107 Leipzig, Germany) ,  Stadler Peter F. (Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22, D-04103 Leipzig, Germany) ,  Stadler Peter F. (German Centre for Integrative Biodiversity Research (iDiv) Halle-Jena-Leipzig, Competence Center for Scalable Data Services and Solutions, and Leipzig Research Center for Civilization Diseases, University Leipzig, D-04103 Leipzig, Germany) ,  Stadler Peter F. (Fraunhofer Institute for Cell Therapy and Immunology, Perlickstrasse 1, D-04103 Leipzig, Germany) ,  Stadler Peter F. (Institute for Theoretical Chemistry, University of Vienna, Waehringerstrasse 17, A-1090 Wien, Austria) ,  Stadler Peter F. (Center for RNA in Technology and Health, Univ. Copenhagen, Gronnegardsvej 3, 1870 Frederiksberg C, Denmark) ,  Stadler Peter F. (Santa Fe Institute, 1399 Hyde Park Rd., Santa Fe, NM 87501, USA)
資料名： Algorithms (Web)  (Algorithms (Web))
巻： 10  号： 4  ページ： 135  発行年： 2017年 
JST資料番号： U7130A  ISSN： 1999-4893  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： スイス (CHE)  言語： 英語 (EN)

抄録/ポイント： ストリング文法がどのようにしてストリングを作り出すかについて記述するところで,木文法は木の生成と構文を記述する。一般化代数動的計画法を木文法に拡張する方法を示した。得られた動的プログラミングアルゴリズムは効率的であり,効率的なバックトラッキングのための外部パーサと代数製品の自動生成を含む,ストリング文法に利用可能な完全な特徴集合を提供する。完全な構文解析インフラストラクチャは,Haskellにおける埋め込み領域特異言語として利用可能である。形式的フレームワークに加えて,ツリーアラインメントとツリー編集の両方に対する実装を提供した。両方のアルゴリズムは,他の間では,生物情報学の分野において活発に使用されており,そこでは樹木に関する最適化問題がかなり実用的に重要である。このフレームワークと付随するアルゴリズムは,ツリーと森林ベースの入力を持つ複雑な文法を開発するための有益な出発点を提供する。Copyright 2019 The Author(s) All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アラインメント ,  文法 ,  *代数学 ,  構文分析 ,  バックトラッキング ,  インフラストラクチャー ,  言語 ,  アルゴリズム ,  最適化問題 ,  編集 ,  *動的計画法
準シソーラス用語： Haskell ,  自動生成 ,  パーザ ,  構文 , 【Automatic Indexing@JST】

著者キーワード (4件)： 動的計画法 ,  形式言語 ,  ツリー編集 ,  ツリーアラインメント

分類 (4件)： 数理言語学  (JB05000V) ,  人工知能  (JE08000Z) ,  自然語処理  (JE06000L) ,  情報加工一般  (AC05010A)

引用文献 (55件)：

• Bellman, R. On the theory of dynamic programming. Proc. Natl. Acad. Sci. USA 1952, 38, 716-719.
• Sankoff, D.; Kruskal, J.B. (Eds.) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison; Addison-Wesley: Reading, MA, USA; Don Mills, ON, Canada, 1983.
• Hofacker, I.L.; Fontana, W.; Stadler, P.F.; Bonhoeffer, L.S.; Tacker, M.; Schuster, P. Fast folding and comparison of RNA secondary structures. Monatshefte für Chemie/Chem. Mon. 1994, 125, 167-188.
• Lorenz, R.; Bernhart, S.H.; Höner zu Siederdissen, C.; Tafer, H.; Flamm, C.; Stadler, P.F.; Hofacker, I.L. ViennaRNA Package 2.0. Algorithms Mol. Biol. 2011.
• Durbin, R.; Eddy, S.R.; Krogh, A.; Mitchison, G. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids; Cambridge University Press: Cambridge, UK, 1998.

タイトルに関連する用語 (2件)： 代数 ,  動的計画法