带约束星形序列比对复杂性的研究

摘要：

本文系统介绍了生物信息学中的非常重要的序列比对问题，并针对带约束的星形多序列比对进行了深人的研究，证明了在某些给定的打分矩阵下，带约束的星形多序列比对是不存在常数近似度的多项式算法。

关键词： 生物信息 基因序列 计算机比对

作者: 王盛 吴长刚 孙慰迟

作者单位: 复旦大学计算机科学与工程系,上海,200433 河北农业大学理学院,保定,071001

会议类型: 国内会议

会议名称: 2006年全国理论计算机科学学术年会

会议地点: 长春

会议语种:中文

页码: 122-124

在线出版日期: 2006-08-09（万方平台首次上网日期，不代表论文的发表时间）