CAJ | 학술논문

本文研究了一个蛋白质相似性搜索问题，即在满足mRNA二级结构互补约束且不含终止密码子的条件下，寻找与给定的mRNA和蛋白质有最大相似性的mRNA序列和编码氨基酸序列的问题，简称MRSOS问题。讨论了该问题的复杂性，同时，结合RNA分子二级结构的实际特征，考虑了该问题在相应结构图最大度为1的限制情形，简称为MRSOS-D1问题，讨论了此问题的复杂性，并给出了MRSOS-D1问题的7-近似算法。
본문연구료일개단백질상사성수색문제，즉재만족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.