文献

J-GLOBAL ID：201902246682855619   整理番号：19A2525703

最長共通部分列による不完全シーケンスの比較【JST・京大機械翻訳】

Comparing incomplete sequences via longest common subsequence

著者 (4件)： Castelli Mauro (NOVA Information Management School (NOVA IMS), Universidade Nova de Lisboa, Campus de Campolide, 1070-312, Lisboa, Portugal) ,  Dondi Riccardo (Dipartimento di Scienze umane e sociali, Universita degli Studi di Bergamo, Italy) ,  Mauri Giancarlo (Dipartimento di Informatica, Sistemistica e Comunicazione, Universita degli Studi di Milano-Bicocca, Milano, Italy) ,  Zoppis Italo (Dipartimento di Informatica, Sistemistica e Comunicazione, Universita degli Studi di Milano-Bicocca, Milano, Italy)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 796  ページ： 272-285  発行年： 2019年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 足場充填に触発されて,不完全データからのゲノム再構成のための最近のアプローチ,2つの配列の比較のためのよく知られた最長共通サブシーケンス問題の変異体を考察した。Longest Filled Common subsequenceと呼ばれる新しい問題は,完全なシーケンスを不完全なものと比較することを目的としている。完全配列A,不完全配列B,およびBにおける記号欠損の多重集合Mを与えた最長のフィルタリングCommon subsequence(LFC)は,BにMのシンボルを挿入することにより得られたB*を,最大長のAを伴う共通のサブシーケンスを誘導する。この問題の計算と近似の複雑さを調べ,Aが各記号のほとんどの2つの発生を含むときNP困難で,APX困難であることを示し,入力系列が一定サイズのアルファベット上にある場合に多項式時間アルゴリズムを与えた。Longest Filled Common Subsequence問題に対する35近似アルゴリズムを与えた。最後に,Bに挿入されたシンボルの数によってパラメータ化されるとき,問題のための固定パラメータアルゴリズムを提示する。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 近似法 ,  ゲノム ,  パラメタリゼーション ,  *アルゴリズム ,  フィルタリング ,  再構成 ,  NP困難
準シソーラス用語： 近似アルゴリズム ,  多項式時間アルゴリズム ,  多重集合 ,  不完全データ ,  *最長共通部分列 , 【Automatic Indexing@JST】

著者キーワード (5件)： 最長共通部分列 ,  ストリングアルゴリズム ,  近似アルゴリズム ,  計算の複雑さ ,  固定パラメータアルゴリズム

分類 (2件)： 計算理論  (JB02000A) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (2件)： 最長共通部分列 ,  シーケンスの比較