一个蛋白质相似性搜索问题的近似算法

An Approximation Algorithm for Protein Similarity Search Problem

本文研究了一个蛋白质相似性搜索问题,即在满足mRNA二级结构互补约束且不含终止密码子的条件下,寻找与给定的mRNA和蛋白质有最大相似性的mRNA序列和编码氨基酸序列的问题,简称MRSOS问题.讨论了该问题的复杂性,同时,结合RNA分子二级结构的实际特征,考虑了该问题在相应结构图最大度为1的限制情形,简称为MRSOS-D1问题,讨论了此问题的复杂性,并给出了MRSOS-D1问题的7-近似算法.

A protein similarity search problem has been studied in the paper. For a given mRNA and a protein, we try to seek a sequence of nucleotides which has the maximal similarity to the given mRNA and its induced protein sequence is maximally similar to the given protein as well. Additionally it obeys complementary constraints and does not contain any stop codon. This is named as the MRSOS problem. The complexity of the MRSOS problem is evaluated. The complexity of a restricted version of the MRSOS problem, i.e., the corresponding structure graph has a maximum degree of one, denoted as MRSOS-D1 problem, is also discussed. The 7-approximational algorithm for the MRSOS-D1 problem is provided.