更新履歴

• 28th September, 2021 (JST): コンテスト終了に伴い，テストケースを削除しました．また，サンプルデータの配布も終了しました．D問題は，問題文のみの公開となります．プログラムを提出してもジャッジは行われません．コンテスト開催時の実行時間制限は30秒でした．
• 11th September, 2021 (JST): サンプルデータのダウンロードに必要な情報を追記しました．
• 10th September, 2021 (JST): Sample2 終端記号が抜けているのを直しました. 本文中の f = 0 という誤りを f = > に修正しました．ダウンロードできるサンプルデータに - や X が含まれる理由の解説を加えました．
• 9th September, 2021 (JST): ダウンロードデータセットに関する注意書きを追加しました．
• 9th September, 2021 (JST): 日本語の問題文を公開しました．ジャッジサーバーが動いています．

追加情報（トップページより転載）

• 2021/9/12 : D問題に関しまして，Dockerによる手元ジャッジ環境を準備しました．こちら(GitHub)よりダウンロードできます．手元でのジャッジの他，入力のパース，非常に基本的な解を出力するプログラムも含まれております．
• 2021/9/12 : D問題に関しまして，BAM形式のビューア―の使い方を記載した資料を準備しました．こちらからダウンロード頂けます．

ストーリー

あなたは Oxford Nanopore Technologies 社の最新機器である PromethION を手に入れた！PromethION は DNA を読み取る機械である．この機械を用いてあなたは自分の DNA 配列を解析しようと試みた．しかし，PromethION はあなたの DNA 配列を端から端まで100%正確に読み取れるわけではない．PromethION に投入するために DNA を精製すると，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 の逆相補鎖（逆相補鎖問題の定義はＡ参照）を代入する． 代入したときには f = <, そうでないときには f = > とする．f=< の場合であっても最終的な結果 B に含まれるペアワイズアラインメントは r と同じ向きに揃えられていることに注意せよ．ただし，B には各文字列がもともとどちらの向きであったかを示す情報（すなわち f ）が含まれている．

(6) t を観測してf と文字列を出力する． 文字列観測の際にはエラーが発生する． エラーの種類には, 文字が別の文字に置き換わってしまう置換, 文字が増減する挿入や欠失がある． 詳しくは観測エラーについての補足を参照のこと．

くだけた問題の説明

実際の観測試行では始点の座標と終点の座標がバラバラであり，n 本の観測試行を重ねて表示したものを縮小して表示した一例を以下に示す．A, C, G, T がそれぞれ異なる色に割り当てられており，スペース節約のために観測試行はなるべく上に詰めて表示している．また，各観測試行の端にグレーの三角印が付いているが観測試行の向き f を表している．大きな欠失は細い水平の黒線で表されており，挿入は潰れて認識しにくく表示されている．

観測エラーについての補足

観測エラーは置換，挿入，欠失の３種類からなる．観測エラーはシミュレーションではなく実機の PromethION と開発中の試薬を用いることで結果として含まれているため，どのような時にどれぐらいの頻度でどのようなエラーが入るかは出題者にも厳密には分からない．観測エラーの性質を分析できるように，既知の DNA 配列を PromethION で読んだデータが別途ダウンロード可能である（後述）．

置換

ある文字が別の文字に置き換わる．以下の例では２文字目の 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 である

入力例 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 の利用方法については今後追記される．また，入力データと解答データを元に皆様の手元の計算機上で採点できるように採点プログラムを用意した．このプログラムを用いて手元の計算機で採点する場合には一切の制限がないため，デバッグや開発に役立てて欲しい．

以下の Answer Data には２行で秘密配列 s_1, s_2 に相当する配列が格納されている。但し、ジャッジが採点する際にスコアを高速に計算できるように s_1 と s_2 の正解ペアワイズアラインメントを作成し - を挿入することで長さを等しくしてある．実際に参加者が submit するべきプログラムはこのような - を挿入してはいけない．また、Answer Data には X という文字も含まれているが，これは採点に用いない配列領域を表している．本コンテストで用いたデータは本物のヒトDNA配列を用いているため，（参加者に提供したデータとは独立に取得した膨大な観測データからは）現在の科学レベルでは自信をもって確定できない DNA 配列が残っており，そのような領域を採点から外すためにマスクしてある．X に対応する領域は文字や文字の長さを間違えてもペナルティは課されない．

※本データセットは本コンテストに供するために Oxford Nanopore Technologies 社から提供されたデータを含んでいます．ここでダウンロードしたデータをコンテスト以外の目的に利用することはできません．また，コンテスト終了後にはデータは消去してください． 採点プログラム（gen1_small_10.testcase.txtを含む）と以下のデータのダウンロードには，IDとパスワードの入力が必要です．IDは「genocon2021」パスワードは「ontQ20」となります．IDとパスワードは他所にて開示することはしないでください．

• gen1_small10
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index
• gen1_small12
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index
• gen1_small13
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index
• gen1_small14
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index
• gen1_small15
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index
• gen1_small17
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index
• gen1_small18
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index
• gen1_small19
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index
• gen1_small20
  • Input Data
  • Answer Data
  • Sorted BAM
  • Sorted BAM Index

断り書き

本問題で提供するデータは Oxford Nanopore Technologies 社の開発している PromethION DNA シークエンサーと，一般にはまだ販売されていないQ20試薬を用いた同社提供の（公開許諾済みの）ヒトゲノムデータから作成していますが，今回提供されたデータは開発中の試薬を用いているため今後製品として同製品の一般販売が開始された場合の製品の性能を示すものではありません．

問題の背景

※ この項目は読まなくても問題を解くことができますが，出題の背景となりますため，ご興味を持ってくださった方はお読みいただけると幸いです．

DNA の配列（A, C, G, T）を読み取る機械である DNA シークエンサーは染色体の端から端までを誤り無く読み取ることはできない．細胞からDNAを抽出する際に DNA が痛んでしまい，細かく千切れてしまうため，DNAシークエンサーのセンサー部分に全長の染色体をセットすることがそもそも不可能である．このため，現実世界では細かく千切れた DNA 断片の配列をたくさん読み取ってコンピューター処理により元々の DNA 配列を推定し復元する．読み取った DNA 配列は千切れているため，染色体のどの部分を読んだのかが分からず，染色体上のどこかランダムな位置から読まれた断片配列が読み取られる．

読み取った断片配列が染色体上のどこから読まれた配列であるかは，ヒトの場合にはヒト参照ゲノムと呼ばれる標準的なヒトゲノム配列に対してペアワイズアラインメントを行うことで調べている．概ね９割ぐらいのヒトDNA配列はほとんど全ての人類で同じような順序で並んでいる．つまり，ヒト参照配列にマッチングを行うことで染色体のどの部分から出てきた断片配列であるかが分かる，ということである．残りの１割は標準的なヒト参照ゲノム配列に対してマッチングする場所が２箇所以上あり，染色体上のどこから得られた断片なのかが確定できなかったり，標準的な参照ヒトゲノム配列にはそもそも存在しない配列だったりする．

今回のコンテストで提供するデータは匿名の複数の人物から「世界中にデータを公開しても良い」という条件で頂いた DNA を実際に PromethION シークエンサーと最新のQ20試薬で読んだ断片配列を用いて作成している．コンテスト参加者に配っているサンプルデータからジャッジに用いるデータが類推できないように，コンテスト参加者に配ったデータとジャッジに用いるヒト DNA断片配列は異なる人物から得られた DNA 配列断片である．以下のスクリーンショットは IGV と呼ばれるゲノム断片配列ビューアーを用いて実際のデータを表示している例である．

観測試行の (1) において 50% の確率で方向を選んでいるのは DNA の２重螺旋のうちどちら側が DNA シークエンサーによって読まれるかを模しており，基本的に現実世界でも 50% の確率で２重螺旋のどちら側が選ばれるかが決まると思われている．ただし，実際にそれが成り立っているかどうかは誰も知らない．読み取った断片配列を参照ヒトゲノム配列にマッチングさせた際に方向を揃える処理を行うことが一般的であり，上記のスクリーンショットでは参照ヒトゲノム配列の方向に合わせて断片配列の向きを全て揃えてある．

観測試行の (2) では DNA 断片の長さを決めている．実際の分布はDNA断片を細胞から抽出する際の実験条件等に依存して複雑な形をしており，具体的な分布を事前に示すことは難しい．

DNAシークエンサーで読み取り可能な断片配列長は技術の進歩とともにどんどん長くなり，2000年頃には 1200 文字（1200塩基対）程度だった最大読み取り長は，PromethION ではほぼ無限と言われている．ただし，DNA 断片配列を壊さずにシークエンサーにセットできた世界最長の記録は 400万文字（400万塩基対）程度と言われている．何れにせよ，DNAは通常もっとずっと短く千切れてしまっているので連続した読み取り長は 1,000 文字から10万文字ぐらいとなるのが普通である．

DNAシークエンサーの読み取りは完璧では無く，観測エラーが発生する．このため，DNAシークエンサーにセットした DNA の配列とは若干異なる配列が読み取られて出力されることが多い．エラーがどのようなメカニズムで発生してどのような性質（分布）を持っているのかは科学的な興味の対象である．今回提供した PromethION の Q20+試薬を用いたデータは Oxford Nanopore Technologies が開発した最新の試薬を使っているため，エラーの性質（分布）については未知の部分も多い．簡単に言うと出題者にも確かなことは言えない，ということである．旧バージョンの試薬では多くの（6文字以上）連続した AやTを読み取ろうとすると真の長さより短くなってしまう傾向があることが知られていた．今回の新試薬ではこのようなエラーが大きく減っていることが期待される．PromethION シークエンサーの小型版である MinION の動作原理について同社の動画（英語）がアニメーションで詳しく解説している．余裕があれば動画をぜひ見て欲しい．PromethION はポア（ＤＮＡを検知するセンサーの穴）の数が MinION より多いが，基本的な動作原理は同一である．

今回，参加者の皆様には参照ゲノム配列と PromethION の出力データの一部をお配りするので，新型試薬の観測エラー（シークエンシングエラー）の性質を推定し，２本の DNA 配列（ゲノム配列の一部）をなるべく正しく推定するプログラムを書いて欲しい．余談とはなるが，研究現場で最終的に達成したい精度は，エラーが 1,000,000 文字（塩基）につき 1塩基以下である．今回の問題で言えば全ての問題について満点に相当する．過去に行われた別のプログラミングコンテストでは，DNA 配列解析とは全く無縁のプログラマーが研究業界トップのプログラムを（コンテストで設定された基準で）超えるパフォーマンスをたたき出したと聞く．このコンテストでも業界トップの既知のアルゴリズムを超えるアルゴリズムが産まれたりはしないかと密かに期待をしているところである．Oxford Nanopore Technologies 社もおそらく同様の期待を抱いてのことだとは思うが， DNA 配列シークエンシングを行い本コンテストへのデータ提供を承諾してくれた．もしこの試みが上手く行けば PromethION を用いたゲノム解読が進歩して，がんの治療法やさまざまな遺伝病の原因発見が大きく加速するかも？