← 返回题目列表

AtCoder · genocon2021_d

D. 注意差异

中文机器翻译题面 查看原题

更新履歴

  • 2021 年 9 月 28 日(日本标准时间): 由于比赛结束,测试用例已被删除。此外,样本数据的分发已经结束。对于问题D,仅公开问题正文。即使您提交了程序,也不会做出任何判断。比赛时的执行时间限制为30秒。
  • 2021 年 9 月 11 日(日本标准时间):添加了下载示例数据所需的信息。
  • 2021 年 9 月 10 日(日本标准时间):更正了 Sample2 中缺少的终端符号。将文中错误f=0更正为f=>。可下载的样本数据 添加了对为何包含 - 呀 可以表示一个整数,例如 X 的解释。
  • 2021 年 9 月 9 日(日本标准时间):添加了有关下载数据集的注释。
  • 2021 年 9 月 9 日(JST):日语问题文本已发布。判断服务器正在运行。

附加信息(从首页转载)

  • 2021/9/12:关于问题D,我们使用Docker准备了本地判断环境。这里 (GitHub) 可以从下载。除了手头的判断之外,还包括解析输入并输出非常基本的解决方案的程序。
  • 2021/9/12:关于问题D,我们准备了一份文档,描述如何使用BAM格式查看器。单击此处下载它。

故事

您已获得 Oxford Nanopore Technologies 的最新设备 PromethION! PromethION 是一台读取 DNA 的机器。您尝试使用这台机器分析您自己的 DNA 序列。但是,PromethION 无法以 100% 的准确度端到端读取您的 DNA 序列。当 DNA 被纯化并输入 PromethION 时,DNA 会被撕成碎片。因此,一次观察得到的序列只是DNA序列的一部分。此外,由于存在观察误差,从已读取的 DNA 序列片段集合中准确预测您的 DNA 序列并不容易。您的任务是从 PromethION 的输出数据推断您的真实 DNA 序列。你的 DNA 中有两种序列,一种遗传自你的父亲,一种遗传自你的母亲,你希望尽可能准确地猜出它们。 包括

問題文

文字A, C, G, T组成 2 书的秘密字符串 s_1, s_2 存在。s_1, s_2 在很多情况下匹配率超过99%,但也有存在显着差异的情况。 s_1, s_2 的长度是 l_1, l_2 。对两个秘密字符串执行以下观察和操作的结果是: 使用 B 。B 中的信息猜测秘密字符串, 输出两个尽可能可能为s_1, s_2 的字符串。

(1) 对于观察,进行以下“观察试验”。 这是通过重复n 次来完成的, n 获取书籍的字符串。

(2) 在观察试验中获得 n 对书籍的字符串执行以下操作。

(2a) 与 s_1, s_2 类似(或者提问者认为)的数组 r 存在。这个数组 r 是在观察试验中获得的。 n 成对对齐书中的每个字符串(成对对齐的定义参见问题B)

(2b) 配对比对结果 (n 件)和 合并 r 并得到结果 B 。结果 包含在 B 中 n 成对比对全部对齐 它与 r 沿相同方向对齐。

観測試行

(1) s_1 和 s_2 的概率为 50%,所选字符串为 s_i 。

(2) 选定的字符串 起点相对于s_i的坐标b 均匀随机 (-l_i \le b \le l_i) ,终点坐标 e 的 e - b 被确定遵循一定的分布。 e 是 没有时间大于 0 如果发生以下情况,请从 (1) 重新开始观察试验。

(3) b 是 没有时间大于 1 如果小于或等于 替换 b 至 将计算结果赋值给同一个变量的操作,如加 1 。 e 是 没有时间大于 l_i 如果大于 e 至 将计算结果赋值给同一个变量的操作,如加 l_i 。

(4) t = s_i [b: e] (s_i 的 b 从第一个字符开始 e 字符)。

(5) 概率为 50% 代入 t 至 将计算结果赋值给同一个变量的操作,如加 t 的反向互补链(反向互补链问题的定义见A)。当你替代时 f = <,否则 最终结果即使 f = > 。f=< 最终的结果即使 B 中包含的成对比对是 请注意,它的对齐方向与 r 相同。然而,B 包含指示每个字符串最初朝向哪个方向的信息(即 f )包含在内。 观察

(6) t 输出字符串f 。观察字符串时发生错误。错误类型包括用另一个字符替换一个字符置換,字符增加或减少 有挿入呀 可以表示一个整数,例如欠失。了解更多详情关于观察误差的补充 请参阅。

非正式问题解释

[原图]

在实际的观察试验中,起点坐标和终点坐标是不同的,因此下面是n个观察试验的缩小显示示例。 A、C、G 和 T 分别分配不同的颜色,观察试验尽可能靠近顶部显示以节省空间。另外,每个观察试验的边缘都附有一个灰色三角形标记,但观察试验的方向是 它代表 f 。大的缺失由细水平黑线表示,插入看起来折叠且难以识别。

[原图]

关于观察误差的补充 请参阅

观察错误包括三种类型:替换、插入和删除。观察误差是由于使用实际的 PromethION 和正在开发的试剂而不是模拟而导致的,因此即使提问者也不知道确切的时间、频率和类型的错误会发生。为了分析观察误差的性质,可以单独下载使用 PromethION 读取已知 DNA 序列所获得的数据(稍后描述)。

置換

一个字符被另一个字符替换。在下面的示例中,第二个字符 它已被 C 是 没有时间大于 G 取代。

元文字列 : ACCAG
観測文字列: AGCAG

挿入

将原始字符串中不存在的数组(任意长度)添加到观察到的字符串中。在下面的示例中,原始字符串的第二个和第三个字符之间 已插入 AA 。

元文字列 : ACGAG
観測文字列: ACAAGAG

欠失

原始字符串中存在的数组(任意长度)不会出现在观察到的字符串中。在下面的示例中,它存在于原始字符串的第三个字符中。 观察到的字符串中缺少 G 。 它是一个由

元文字列 : ACGAG
観測文字列: ACAG

制約

  • s_1, s_2表示A, C, G, T组成的字符串。
  • 3 \leq l_1, l_2 \leq 101,000。
  • n \le 200 是

入力

输入是按以下格式从标准输入给出的。

g
f_{1} r_{1} c_{1}
f_{2} r_{2} c_{2}
 :
f_{n} r_{n} c_{n}
=

观察到的DNA片段序列是 n 这个是给出的,但是为了节省输入数据大小 n 本书的序列以压缩符号给出,以标准 DNA 序列及其差异的形式给出。第一输入线 g 是标准DNA序列,1 文字以上 101,000 一个或更少的字符串。

然后输入 2 我将解释该行之后发生的情况。 在2 从行n+1 行中,每行写入一个观察到的DNA片段序列。每行的第一个 f_i 给出 DNA 相对于参考序列的方向。 DNA的方向是向右(g 同方向) > 向左 (g (反向互补链方向) 给出了 < 。尽管不使用该信息也可以在一定程度上解决该问题,但众所周知,错误趋势因DNA的方向而异,因此预计通过积极使用该信息将有可能提高分数。 r_{i}, c_{i} 对代表观察到的压缩形式的 DNA 片段序列。具体来说 该差异是基于 g 的一部分来表达的。首先,g 的 r_i 文字目(r_i 是 0 源,第一个字符是 将光标置于 0 字符处。c_i 是由三元组{长度}{类型}{辅助信息}的零次或多次重复组成的字符串。 {Length}表示为任意长度的数字,{Type}为1个字符。 {辅助信息}可能存在也可能不存在,具体取决于{Type}的类型,但如果存在辅助信息,则{辅助信息}是一个由{Length}指定长度的字符串;否则,{辅助信息}为空字符串。

“类型”是指参考基因组序列。 代表一致代表=和不一致代表 X ,以及来自参考数组欠失代表 D,来自参考数组 有四种类型:挿入代表 I 。

输入结束是 它由仅包含 = 的行给出。 (n 表示 = 隐含地给出了出现之前的行数)

解释有关“类型”的详细信息,一致,不一致,欠失,挿入每个的具体示例如下所示。

匹配示例 使用

観測試行回数 n=1 的示例一致已解释。下面所示的是一个输入示例,其中仅输入一个数组,以及与其对应的一个观察数组。

ACGTGCTTA
> 0 6=
=
ACGTGC

6= 是一条从标准基因组上当前光标位置获取并输出 6 个字符的命令。r=0 并且光标位于左边缘,因此 检索g 的前 6 个字符,ACGTGC 获得 作为输出。

显示了另一个输入示例和与其对应的一个观察数组。

ACGTGCTTA
< 2 4=
=
GTGC

此示例演示如何更改初始光标位置。光标位置是从头开始跳过的两个字符,从那里输出四个字符。 GTGC 输出 。如果匹配,则将光标位置向右移动输出的字符数。

在以下输入示例中: 2= 和 3= 已连接,但这是 与5= 含义相同,从光标位置复制输出5个字符(2+3个字符)。结果,观察到的数组是 CGTGC 变为。

ACGTGCTTA
< 1 2=3=
=
CGTGC

不匹配示例

如果您想输出与标准基因组不同的字符,请输入 使用 X 。 {长度}X如果给定字符串{content},则输出{content}并将光标向右移动长度。在下面的示例中输入

ACGTGCTTA
> 0 3=2XGA4=
=

3=(3文字一致)和2XGA(2文字 GA 并将光标前进两个字符)4=4文字一致不断执行,观察到的数组代表下面的字符串。

ACGGACTTA

对应关系可以以易于阅读的方式写成如下。标准基因组 g 观察到的数组是 显示为 A 。为了方便查看,在匹配的字符之间 | 不匹配的字符之间。 已写入 X 。

g: ACGTGCTTA
   |||XX||||
A: ACGGACTTA

删除示例

如果标准基因组中有缺失,请输入 如果给出字符串 D 。 {长度}D ,它将把光标向右移动长度,而不输出任何内容。在下面的输入示例中,从坐标 1 开始(从开头跳过一个字符) 2= (2文字一致), 1D (1文字欠失(削除)),4=(匹配 4 个字符)。

ACGTGCTTA
< 1 2=1D4=
=
CGGCTT

这个观察阵 A 和标准基因组 g 的对应关系可以写成如下,方便查看。使用观察排列是因为当匹配的字符垂直排列时更容易看到。 插入 A 至 将计算结果赋值给同一个变量的操作,如加 - 并移动数字。

g: ACGTGCTTA
    || ||||
A:  CG-GCTT

插入示例

键入标准基因组中是否有插入。 使用 I 。 {长度}I如果给出字符串{content},则输出{content}而不前进光标。在下面的输入示例中,从坐标 2 开始(从开头跳过 2 个字符) 2= (2文字一致), 2IAT (2文字AT),3=(3个字符匹配),输入示例及对应的观测数组如下。

ACGTGCTTAG
> 2 2=2IAT3=
=
GTATGCT

类似的标准基因组 g 和观察阵列 A 的对应关系可以写成如下,方便查看。垂直排列时更容易看到匹配的字符。 插入并显示 g 至 将计算结果赋值给同一个变量的操作,如加 - 。

g: ACGT--GCTTAG
     ||  |||
A:   GTATGCT

关于压缩符号的补充

标准 DNA 序列和n 书中观察到的字符串之间的对应关系是使用基因组学行业的标准工具之一计算的,因此在大多数情况下序列之间的关系可以被认为是正确的。但请注意,有些地方对应不正确。例如,在下面的例子中,标准基因组 g 和待观察的基因组 即使 T 之间的真实对应关系如下(如果上帝存在并且我们知道DNA测序仪的观察错误是如何发生的,并且我们将真正对应的字母逐一排列),观察到的序列 可能会输出不正确的对应关系,例如A 。

g: ACGTGCGTAGCG
   |||  |  ||||
T: ACG--C--AGCG
   |||     ||||
A: ACGC----AGCG

输入中经常包含此类排序错误,但可以通过纠正这些错误来提高您的分数。

另外,由于压缩符号的处理不是比赛的主要焦点,因此将从 Python 中的压缩符号生成多重对齐(多重对齐参见问题 C),以便于参赛者更轻松地进行调试。 Python 3 的示例代码 我已经准备好了 。如果您提供此问题的示例输入数据文件作为第一个参数,它将以文本格式输出多重对齐。

出力

将两个猜出的秘密数组分成两行,每行输出一个数组。在输出数组中 它不得包含除 A, C, G, T 之外的任何字符。另外,请务必在第二行末尾使用换行符。

分数

两个输出数组 o_1, o_2 。如果 如果替换 o_1, o_2 会增加分数,则计算替换后的分数。 比较

o_1 和 s_1, o_2 和 s_2 ,每次正确一个字符 给出 0.01 点。每 1 个字符错误答案(1 个字符替换、1 个字符删除、1 个字符插入) 0.99 丢分。

然而,在某个坐标 马赛克化如果这样做分数增加,则执行马赛克并计算分数。马赛克化是一种操作,可用于纠正在序列中途交换时估计两个秘密序列时出现的错误。 下面显示了 马赛克化的示例。下面的例子中,恢复的秘密字符串在中间的一点进行了交换(为了强调,插入了一个空格,这个空格的坐标称为马赛克坐标),但是在马赛克时,在马赛克坐标的前后进行了替换。 o_1, o_2 的数组是可以交换的,下面的例子中,通过拼接, o_1, o_2 中包含的所有字符 s_1, s_2 。然而,马赛克最多只能进行一次,并且这样做会受到惩罚。7.5丢分。

马赛克示例

s_1: GTC ACCGTGCAG
s_2: AACG ACGGACATG

o_1: AACG ACCGTGCAG
o_2: GTC ACGGACATG

关于分数的注意事项 1

该问题的输入数据是完全真实的数据。换句话说,实际的人类DNA序列被输入DNA测序仪,并且输出数据的一部分被切出并使用。此外,这两个正确的序列是通过使用各种仪器(包括 DNA 测序仪)观察实际人类 DNA 序列而获得的大量数据中收集接近行业最佳知识的知识而创建的。这意味着不能保证从输入数据中可以输出两个具有满分的数组。此外,虽然评委用作正确答案数据的数据被认为是极其准确的,但它并不一定是100%正确的。人们认为,存在许多问题文本中未提及的偏见。如有疑问,请始终相信数据。

关于分数的注意事项 2

在这个问题中,我们希望对现实世界中更有用的答案给予更高的分数。因此,我们只想针对当前上传到服务器的低分数据集来评估过拟合算法的答案。例如,我想通过使用随机数种子创建一个算法,上传许多具有不同种子的答案,并使用获得最高分数的随机数种子作为最终版本,来减少现实世界中无用的答案的分数。因此,评委数据将在节目提交截止日期后添加到最终得分中。理论最高总分目标为30,000分,但由于是基于实际数据,因此存在10%左右的误差,敬请注意。

样本 1

这是一种具有两种类型的短秘密字符串的模式。


入力例 1

ACACAGCGGCGACC
> 0 3=1XT10=
< 0 14=
< 0 9=1D4=
< 0 14=
< 0 14=
< 0 9=1D4=
=

出力例 1

ACACAGCGGCGACCT
ACATAGCGGGACT

输入以多重对齐格式显示,以便于查看

G 表示参考数组。

  G  : ACACAGCGGCGACC
  0 >: ACATAGCGGCGACC
  1 <: ACACAGCGGCGACC
  2 <: ACACAGCGG-GACC
  3 <: ACACAGCGGCGACC
  4 <: ACACAGCGGCGACC
  5 <: ACACAGCGG-GACC

样本 2

这是一种模式,其中两种类型的短秘密字符串完全相同,或者即使存在差异,也无法从输入确定差异。


入力例 2

ACCGGTTGGCGTG
> 0 5=
< 1 8=
> 2 2=1XA3=1IC3=
< 4 5=1D2=
> 7 6=
=

出力例 2

ACCGGTTGGCGTG
ACCGGTTGGCGTG

输入以多重对齐格式显示,以便于查看

  R  : ACCGGTTG-GCGTG
  0 >: ACCGG
  1 <:  CCGGTTG-G
  2 >:   CGATTGCGCG
  3 <:     GTTG-G-GT
  4 >:        G-GCGTG

稍大的样本

裁判服务器的计算资源有限,最多每两小时提交一次。我们准备了一些更实用的样本数据可供下载,以便参与者可以在自己的计算机上检查数据。下面的数据将示例数据转换为 BAM 文件,这是基因组行业的标准格式之一,也是全球最常用的查看器之一。 IGV 可以在 查看。未来将添加有关如何使用 IGV 的信息。此外,您现在可以根据输入数据和答案数据在自己的计算机上评分。计分程序 我已经准备好了。使用本程序在自己的电脑上评分没有任何限制,请使用它进行调试和开发。

下面的答案数据包含一个包含两行的秘密数组。 存储与 s_1, s_2 对应的数组。不过,这样裁判打分的时候可以快速计算出分数。 创建 s_1 和 s_2 的正确成对比对 通过插入 - 使长度相等。参与者实际应该提交的程序是这样的。 不要插入 - 。此外,答案数据还包括 它还包括字符 X ,它代表不用于评分的数组区域。由于本次比赛使用的数据是真实的人类 DNA 序列,因此仍然存在无法在当前科学水平下可靠确定的 DNA 序列(从独立于提供给参与者的数据获得的大量观察数据中),并且这些区域被屏蔽以将其排除在评分之外。 在X 对应的区域,即使字符或字符长度不正确,也不会受到处罚。

*此数据集包括 Oxford Nanopore Technologies 提供的用于本次竞赛的数据。此处下载的数据不能用于比赛以外的任何目的。另外,请在比赛结束后删除数据。 您必须输入您的ID和密码才能下载评分程序(包括gen1_small_10.testcase.txt)和以下数据。 ID为“genocon2021”,密码为“ontQ20”。请不要在其他地方泄露您的 ID 和密码。

免责声明

本期提供的数据是使用Oxford Nanopore Technologies公司开发的PromethION DNA测序仪和Oxford Nanopore Technologies公司提供的人类基因组数据,使用该公司的Q20试剂(已批准发表)创建的。但由于本次提供的数据使用的是仍在开发中的试剂,因此并不表明该产品未来作为产品普遍销售时的性能。

问题背景

※ 不看本条就可以解决问题,但它提供了出题的背景,所以如果你有兴趣,请阅读它。

DNA 测序仪是一种读取 DNA 序列(A、C、G、T)的机器,无法准确无误地从头到尾读取染色体。从细胞中提取 DNA 时,DNA 会被损坏并破碎成碎片,从而无法在 DNA 测序仪的传感器部分设置全长染色体。为此,在现实世界中,我们读取了许多支离破碎的DNA片段的序列,并利用计算机处理来估计和恢复原始的DNA序列。由于读取的DNA序列是片段化的,因此不知道读取的是染色体的哪一部分,并且片段化的序列是从染色体上的随机位置读取的。

[原图]

在人类的情况下,通过针对称为人类参考基因组的标准人类基因组序列进行成对比对来确定读取片段序列在染色体上的位置。几乎所有人类中,大约 90% 的人类 DNA 序列都以相同的顺序排列。换句话说,通过匹配人类参考序列,可以确定片段序列源自染色体的哪一部分。剩下的10%在标准人类参考基因组序列中具有两个或多个匹配位置,并且无法确定该片段在染色体上的哪个位置获得,或者该序列不存在于标准人类参考基因组序列中。

本次竞赛提供的数据是使用我们从多个匿名人士那里收到的 DNA 片段创建的,条件是他们可以将数据发布给全世界,使用 PromethION 测序仪和最新的 Q20 试剂来读取 DNA 片段。为了使得无法从分发给参赛者的样本数据中推断出评委使用的数据,分发给参赛者的数据和评委使用的人类DNA片段序列是从不同人获得的DNA序列片段。下面的屏幕截图是使用称为 IGV 的基因组片段序列查看器显示实际数据的示例。

[原图]

在观察试验的(1)中,以50%的概率选择方向,模拟DNA测序仪读取DNA双螺旋的哪一侧,基本上认为在现实世界中,将以50%的概率选择双螺旋的哪一侧。然而,没有人知道这是否真的成立。当将读取片段序列与参考人类基因组序列匹配时,通常会对齐读取片段序列的方向,在上面的屏幕截图中,所有片段序列都对齐以匹配参考人类基因组序列的方向。

在观察试验的(2)中,确定DNA片段的长度。从细胞中提取DNA片段时,根据实验条件,实际分布具有复杂的形状,并且很难预先显示具体的分布。

随着技术的进步,DNA测序仪可以读取的片段序列的长度变得越来越长,2000年左右的最大读取长度约为1200个字符(1200个碱基对),据说使用PromethION几乎是无限的。然而,据说可以在测序仪中设置而不破坏它的最长DNA片段序列的世界纪录约为400万个字符(400万个碱基对)。无论如何,DNA通常被切成更短的片段,因此连续读取长度通常在1,000到100,000个字符之间。

DNA 测序仪读数并不完美,并且会出现观察错误。因此,经常读取并输出与DNA测序仪中设置的DNA序列略有不同的序列。错误发生的机制及其特征(分布)是科学兴趣的对象。这次使用PromethION的Q20+试剂提供的数据使用了Oxford Nanopore Technologies开发的最新试剂,因此误差的性质(分布)存在很多未知因素。简而言之,即使是提问者也不能肯定地说。旧版本的试剂有很多(6个字符或更多)连续 众所周知,当尝试读取 A呀 可以表示一个整数,例如T时,长度往往比真实长度短。预计这种新试剂将大大减少此类错误。该公司解释了 MinION 的工作原理,MinION 是 PromethION 测序仪的较小版本。動画(英語)用动画详细解释了这一点。如果您有时间,请观看视频。 PromethION 比 MinION 有更多的孔(检测 DNA 的传感器中的孔),但基本工作原理是相同的。

这次,我们将向参与者分发参考基因组序列和 PromethION 的一些输出数据,因此我们希望他们编写一个程序来估计新试剂的观察误差(测序误差)的性质,并尽可能准确地估计两个 DNA 序列(基因组序列的一部分)。附带说明一下,我们希望在研究环境中实现的最终准确度是每 1,000,000 个字符(碱基)误差为 1 个碱基或更少。在这种情况下,所有问题都相当于满分。我听说在过去举办的另一场编程竞赛中,一个与DNA序列分析完全无关的程序员跑赢了研究行业的顶尖程序(根据竞赛中设定的标准)。我暗自希望这次大赛能产生出超越业界顶级已知算法的算法。牛津纳米孔技术公司可能也抱着类似的期望,进行了 DNA 测序,并同意为本次竞赛提供数据。如果这一尝试成功,使用 PromethION 进行基因组解码的进展可能会大大加速癌症治疗方法和各种遗传疾病病因的发现。