文献

J-GLOBAL ID：201702212995464248   整理番号：17A0856881

コンピューティングの歴史限界の問題のための静的定式化問題の解決【Powered by NICT】

A Resolution of the Static Formulation Question for the Problem of Computing the History Bound

著者 (5件)： Matsieva Julia (Department of Computer Science, University of California at Davis, Davis, CA) ,  Kelk Steven (Department of Knowledge Engineering (DKE), Maastricht University, Maastricht, The Netherlands) ,  Scornavacca Celine (Institut des Sciences de l’Evolution de Montpellier (ISE-M), Montpellier, France) ,  Whidden Chris (Fred Hutchinson Cancer Research Center, Seattle, WA) ,  Gusfield Dan (Department of Computer Science, University of California at Davis, Davis, CA)
資料名： IEEE/ACM Transactions on Computational Biology and Bioinformatics  (IEEE/ACM Transactions on Computational Biology and Bioinformatics)
巻： 14  号： 2  ページ： 404-417  発行年： 2017年 
JST資料番号： W1409A  ISSN： 1545-5963  CODEN： ITCBCY  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 進化的データは伝統的に系統樹を介してモデル化されているが,分岐単独では矛盾する系統発生信号をモデル化することができないので,ネットワークを代わりに用いた。祖先組換えグラフ(ARG)を用いて,SNPデータの不和合性セットの進化をモデル化するために,各部位は一度だけ変異することを可能にする。モデルは往々にして再結合の数を最小化することを目的とした。同様に,不適合クラスタデータは網状事象を最小化する網状組織ネットワークで表すことができる。ARG文献は伝統的に網状組織ネットワーク文献から互いに素した。網状ネットワーク文献からの結果の上に組み立てて,我々はARGコミュニティへの関心の未解決の問題を解決した。歴史結合した,二成分マトリックス,以前にのみ手続き的に定義されたARGにおける再結合の数の下限,対応するクラスタデータのためのネットワーク中の細網化ノードの最小数に等しいことを証明した。証明を容易にするために,手続き的歴史結合定義からの中間値を用いてこのネットワークを構築するアルゴリズムを与えた。歴史結合した,既知の動的プログラムと同程度の最悪実行時間を計算するためのトップダウンアルゴリズムを開発し,典型的な例における速い速度で動作する可能性があることを示した。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： アルゴリズム ,  系統発生 ,  再結合 ,  *定式化 ,  ネットワーク ,  系統樹 ,  不和合性 ,  コミュニティ ,  モデリング ,  モデル
準シソーラス用語： 互いに素 , 【Automatic Indexing@JST】

分類 (2件)： 信号理論  (ND02020G) ,  数値計算  (JE02000J)

タイトルに関連する用語 (5件)： コンピューティング ,  歴史 ,  限界 ,  定式化 ,  問題