问题描述

脱氧核糖核酸（DNA）由一系列相互配对的核苷酸碱基组成，形成双链螺旋结构。通过一系列复杂的生化过程，生物体DNA中的核苷酸序列会被翻译成其生命活动所需的蛋白质。此问题的目标是编写一个计算机程序，该程序接收一条DNA链，并报告由该DNA链生成的蛋白质（如果有的话）。

构成DNA的核苷酸碱基有腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶（以下分别简称为A、C、G和T）。这些碱基在链中相互结合，形成DNA链的一半。DNA链的另一半是类似的链，但每个核苷酸都被其互补碱基所取代。碱基A和T互补，碱基C和G也互补。这两条“半链”DNA通过互补碱基的配对结合在一起，形成一条完整的DNA链。

通常，一条DNA链只需写下构成主链的碱基即可表示（互补链总能通过写出主链中碱基的互补碱基来生成）。例如，序列TACTCGTAATTCACT表示一条DNA链，其互补链为ATGAGCATTAAGTGA。注意，A总是与T配对，C总是与G配对。

在一个被称为转录的过程中，从DNA主链会产生一条被称为信使核糖核酸（简称mRNA）的核糖核酸链。转录得到的mRNA与互补DNA链相同，只是胸腺嘧啶被一种名为尿嘧啶（以下简称为U）的核苷酸所取代。例如，上一段中DNA对应的mRNA链为AUGAGCAUUAAGUGA。

正是mRNA中的碱基序列决定了将要合成的蛋白质。mRNA中的碱基可以看作是一系列密码子的集合，每个密码子恰好由三个碱基组成。密码子AUG标志着蛋白质序列的起始，而密码子UAA、UAG或UGA中的任何一个则标志着序列的结束。起始密码子和终止密码子之间的一个或多个密码子代表了合成蛋白质所需的氨基酸序列。例如，mRNA密码子AGC对应氨基酸丝氨酸（Ser），AUU对应异亮氨酸（Ile），AAG对应赖氨酸（Lys）。因此，上一段示例mRNA形成的蛋白质的缩写形式为Ser - Ile - Lys。

将密码子翻译成氨基酸的完整遗传密码如下表所示（注意，表中仅显示了氨基酸的缩写）。还需注意的是，序列AUG（已被确定为起始序列）也可以对应氨基酸甲硫氨酸（Met）。因此，mRNA链中的第一个AUG是起始序列，但后续的AUG密码子会正常翻译成Met氨基酸。

| 密码子的第一个碱基 | 密码子的第二个碱基 | 密码子的第三个碱基 | | ---- | ---- | ---- | ---- | | | U | C | A | G | | U | Phe | Ser | Tyr | Cys | U | | | Phe | Ser | Tyr | Cys | C | | | Leu | Ser | --- | --- | A | | | Leu | Ser | --- | Trp | G | | C | Leu | Pro | His | Arg | U | | | Leu | Pro | His | Arg | C | | | Leu | Pro | Gln | Arg | A | | | Leu | Pro | Gln | Arg | G | | A | Ile | Thr | Asn | Ser | U | | | Ile | Thr | Asn | Ser | C | | | Ile | Thr | Lys | Arg | A | | | Met | Thr | Lys | Arg | G | | G | Val | Ala | Asp | Gly | U | | | Val | Ala | Asp | Gly | C | | | Val | Ala | Glu | Gly | A | | | Val | Ala | Glu | Gly | G |

输入

该程序的输入是一系列DNA序列，每行一个序列，程序需要确定并输出由这些DNA序列生成的蛋白质（如果有的话）。给定的DNA链可能是主DNA链，也可能是互补DNA链，它可能以正向或反向顺序出现，并且起始和终止序列不一定出现在链的两端。例如，用于形成蛋白质Ser - Ile - Lys的给定输入DNA链可以是ATACTCGTAATTCACTCC、CCTCACTTAATGCTCATA、TATGAGCATTAAGTGAGG或GGAGTGAATTACGAGTAT中的任何一个。输入将以包含单个星号字符的行结束。

输出

你可以假设输入仅包含有效的大写DNA核苷酸碱基字母（A、C、G和T）。输入的每行长度不会超过255个字符。输入中不会有空白行或空格。有些序列虽然是有效的DNA链，但不会产生有效的蛋白质序列；当输入的DNA链无法翻译成有效的蛋白质时，应输出字符串“*** No translatable DNA found ***”。

输入数据1

ATACTCGTAATTCACTCC
CACCTGTACACAGAGGTAACTTAG
TTAATACGACATAATTAT
GCCTTGATATGGAGAACTCATTAGATA
AAGTGTATGTTGAATTATATAAAACGGGCATGA
ATGATGATGGCTTGA
*

输出数据1

Ser-Ile-Lys
Cys-Leu-His
Ser-Tyr
*** No translatable DNA found ***
Leu-Asn-Tyr-Ile-Lys-Arg-Ala
Met-Met-Ala

提示

设输入串为$S$，与$S$互补的DNA串为$S_v$，依次将下列串作为主DNA链进行测试：

1. $S_v$
2. $S_v$的逆序$S_v'$
3. $S$的逆序$S'$
4. $S$

来源

美国中西部1995年竞赛