【作者】 王盛； 吴长刚； 孙慰迟；

【机构】 复旦大学计算机科学与工程系； 河北农业大学理学院；

【摘要】 <正>1 引言在生物信息学的研究过程中,经常需要通过将研究对象相互比较来寻找对象可能具备的某些特性。序列比对(Sequence Alignment)是最常用和最经典的研究手段。序列比对的理论基础是进化学说,如果两个序列之间具有足够的相似性,就推测二更多还原

【Abstract】 Sequence Alignment is one of the most significant research issues in Bioinformatics, especially the Multiple Sequence Alignment problem. It has beening studied deeply in recent years. In this paper, the Constrained Center-Star Sequence Alignment (CCSA) problem is discussed. Furthermore, for a specified score matrix, we proved that no algorithm can solve CCSA within constant approximation factor in polynomial time.更多还原