AT_genocon2021_c.Practice 3

给定 $m$ 个由字母 A、C、G、T 组成的字符串。现在，可以在每个字符串的任意位置插入表示空白的字符 -，使得所有字符串的长度都变为 $n$，并将这些长度相同的 $m$ 个字符串组成 $m \times n$ 的矩阵 $S$。$S$ 的第 $i$ 行第 $j$ 列的元素记作 $S_{i,j}$（$1 \leq i \leq m,\ 1 \leq j \leq n$）。行向量和列向量分别记作 $S_{i,*}$、$S_{*,j}$。现在，希望通过合理地插入 -，使得每一列尽可能多地出现相同的字符。

为衡量每一列“整齐”的程度，对于长度为 $m$ 的字符串 $t$，定义如下分数 $C$：

$$C(t) = \min_{x \in \{A, T, G, C, -\}} \left| \{ t[i]\ |\ t[i] \neq x\ (i=1,\ldots,m) \} \right|$$

通俗地说，$C(t)$ 表示 $t$ 中出现次数最多的字符以外的字符的个数。例如，$t = $ CCCC-T 时，C 出现次数最多，C 以外的字符 - 和 T 的总数为 2，所以 $C(t) = 2$。又如，$t = $ CCAA-T 时，C 和 A 出现次数相同，任选其一作为 $x$，C 以外的字符 A、-、T 的总数为 4，所以 $C(t) = 4$。

对于 $S$ 的所有列向量，计算 $C(S_{*,j})$，其总和越小，说明输入字符串经过调整后同一列出现相同字符的次数越多。通过在字符串中适当插入 -，使得三条及以上的字符串对齐，这种操作称为多序列比对（Multiple Alignment）。定义所有列的分数总和为 $C_{all}(S) = \sum_{j=1}^n C(S_{*,j})$。

例如，对于 3 个字符串 GGATC, GGAT, GACC，如果按如下方式插入 -：

GGATC
GGAT-
G-ACC

则 $C_{all}(S) = C(S_{*,1}) + C(S_{*,2}) + C(S_{*,3}) + C(S_{*,4}) + C(S_{*,5}) = 0 + 1 + 0 + 1 + 1 = 3$。

给定 $m$ 个字符串 $s_1, \ldots, s_m$，请输出一种多序列比对方案，使 $C_{all}(S)$ 尽可能小。

输入从标准输入读取，格式如下：

$m$ $s_1$ $s_2$ : $s_m$

请输出一种多序列比对方案，使 $C_{all}$ 尽可能小。按照输入顺序输出每个字符串，在适当位置插入 -，使所有字符串长度相同。每一行的长度必须一致，且每一行去除 - 后应与对应输入字符串完全一致。

约束条件

• $s_1,\ldots,s_m$ 均为由 A、C、G、T 组成的字符串。
• small 测试用例：
  • $8 \leq m \leq 10$
  • $80 \leq |s_1|,\ldots,|s_m| \leq 100$（$|x|$ 表示字符串 $x$ 的长度）
• large 测试用例：
  • $35 \leq m \leq 40$
  • $700 \leq |s_1|,\ldots,|s_m| \leq 750$

计分方式

提交的程序会根据“约束条件”中的 small 和 large 两类测试用例进行评测。small 有 2 个用例，large 有 8 个用例。仅在规定时间内输出格式正确的结果才会被计分。small 用例每个得分为 $\max\{200 - \lfloor C_{all}(S) * 0.2 \rfloor, 0\}$，large 用例每个得分为 $\max\{700 - \lfloor C_{all}(S) * 0.1 \rfloor, 0\}$。例如，若仅在规定时间内完成了 2 个 small 用例，则得分为 $ \max{200 - \lfloor C_{all}(S_1) * 0.2 \rfloor, 0} + \max{200 - \lfloor C_{all}(S_2) * 0.2 \rfloor, 0}$（$S_1, S_2$ 分别为两个用例的输出）。

不能保证最优解能达到满分（4500 或 6000 分）。最终排名将在赛后用另一组数据评测。当前评测系统和赛后评测数据的生成方式相同。

数据生成方式

从参考基因组（人类第 22 号染色体）中截取部分子串 $s$，仅包含 A、T、G、C 的区域。对截取的子串模拟测序仪的读取错误（插入、缺失、替换），生成字符串 $s'$。重复多次，组成一个测试用例。测试用例不包含 $s$。具体的错误模拟方式不公开，测试数据可从以下链接下载：

• 测试用例下载

问题背景

※ 本节为出题背景，不影响解题，可选阅读。

多序列比对（Multiple Alignment）与成对比对（Pairwise Alignment）一样，在基因组序列分析的多个场景中都有应用。以病毒变异分析为例：

当感染病毒后，体内会产生大量病毒拷贝，同时 DNA 或 RNA 也会被复制。由于复制精度不是 100%，每次复制都会产生各种变异（替换、插入、缺失等），导致产生许多基因组序列略有不同但大致相似的病毒。通过比较这些略有差异但大致相似的序列，分析变异特征，多序列比对就非常有用。

此外，多序列比对还可用于测序仪读取片段的错误纠正。读取基因组时，为了便于后续修正测序错误，会对基因组同一位置进行多次重复读取。得到的片段序列会包含不同的错误，但通过多序列比对并对每一列进行多数投票，可以纠正这些错误。

由 ChatGPT 4.1 翻译