首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:Hardness Results on Local Multiple Alignment of Biological Sequences
  • 作者:Tatsuya Akutsu ; Hiroki Arimura ; Shinichi Shimozono
  • 期刊名称:IPSJ Digital Courier
  • 电子版ISSN:1349-7456
  • 出版年度:2007
  • 卷号:3
  • 页码:174-182
  • DOI:10.2197/ipsjdc.3.174
  • 出版社:Information Processing Society of Japan
  • 摘要: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.
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有