Hardness Results on Local Multiple Alignment of Biological Sequences

• Item type: Trans(1)
• 公開日: 2007-03-15
• タイトル: Hardness Results on Local Multiple Alignment of Biological Sequences
• タイトル / 言語: en
• タイトル: Hardness Results on Local Multiple Alignment of Biological Sequences
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: Original Papers
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Bioinformatics Center Institute for Chemical Research Kyoto University
• 著者所属: Graduate School of Information Science and Technology Hokkaido University
• 著者所属: Department of Artificial Intelligence Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Bioinformatics Center, Institute for Chemical Research, Kyoto University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Hokkaido University
• 著者所属(英): en
• 著者所属(英): Department of Artificial Intelligence, Kyushu Institute of Technology
• 著者名: Tatsuya, Akutsu; Hiroki, Arimura; Shinichi, Shimozono
• 著者名(英): Tatsuya, Akutsu; Hiroki, Arimura; Shinichi, Shimozono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: This paper studies the local multiple alignment problem which is given protein or DNA sequences to locate a region (i.e. a substring) of fixed length from each sequence so that the score determined from the set of regions is optimized. We consider the following scoring schemes: the relative entropy score (i.e. average information content) the sum-of-pairs score and a relative entropy-like score introduced by Li et al. We prove that multiple local alignment is NP-hard under each of these scoring schemes. In particular we prove that multiple local alignment is APX-hard under relative entropy scoring. It implies that unless P = NP there is no polynomial time algorithm whose worst case approximation error can be arbitrarily specified (precisely a polynomial time approximation scheme). Several related theoretical results are also provided.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper studies the local multiple alignment problem, which is, given protein or DNA sequences, to locate a region (i.e., a substring) of fixed length from each sequence so that the score determined from the set of regions is optimized. We consider the following scoring schemes: the relative entropy score (i.e., average information content), the sum-of-pairs score and a relative entropy-like score introduced by Li, et al. We prove that multiple local alignment is NP-hard under each of these scoring schemes. In particular, we prove that multiple local alignment is APX-hard under relative entropy scoring. It implies that unless P = NP there is no polynomial time algorithm whose worst case approximation error can be arbitrarily specified (precisely, a polynomial time approximation scheme). Several related theoretical results are also provided.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12177013
• 書誌情報: IPSJ Transactions on Bioinformatics （TBIO）; 巻 48, 号 SIG5(TBIO2), p. 30-38, 発行日 2007-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6679
• 出版者 / 言語: ja
• 出版者: 情報処理学会