今年のゴールデンウィークはこれをやろう。(提出期限: 2016/5/6)
https://community.topcoder.com/longcontest/?module=ViewProblemStatement&rd=16683&pm=14187
始める前に適当に訳しておきます。
Broad Institute and Crowd Innovation Lab at Harvard University present Challenge DNAS1
Introduction
DNA is a molecule that carries most of the genetic instructions used in the development, functioning and reproduction of all known living organisms and many viruses.
DNAは生物の機能、再生成で使われる遺伝的な指示のほとんどを伝達する分子です。
For humans, it represents a string of a bit more than 3 billion characters, with the vast majority of them shared by all human beings and the remaining ~0.5% encapsulating all the individual differences between them.
人間においては、0.5%以下の誤差を持った30億以上の文字で表現されます。
A full DNA molecule is too long to be read in one piece. In order to analyze it, we must fragment it into millions of short 150 character strings (calls reads), which can be directly read. Like assembling a jigsaw puzzle, these are then reassembled to obtain the original 3 billion character string.
フルサイズのDNA分子は、読むには長すぎるので、分析する場合には、リードと呼ばれる150文字の切片に分けます。
ジグソーパズルをくみ上げるように元の30億の長さを持つ文字列を得るために再構成されます。
This reassembly can then be used as a reference to aid subsequent sequencing efforts — it is much easier to assemble a jigsaw puzzle if you can use the picture on the box as a guide.
この再構成は、シークエンシング(DNAを構成しているヌクレオチドの塩基配列の決定[gene sequencing]、またはタンパク質のポリペプチド鎖内のアミノ酸配列の決定（protein sequencing）を行う手続き)を助けるリファレンスとして使用されます。
箱に書いてある絵をガイドとして見ながらジグソーパズルを組み上げれば、より簡単になりますよね。
The current challenge is the first in a series of challenges targeting this problem.
It focuses on the easiest but most prevalent case of DNA sequencing: a reference is available, and all of the reads are expected to have well-determined positions on the reference DNA which they can be associ ated with (aligned to).
今回のチャレンジは、この問題シリーズの最初の取り組みで、最も簡単な部類の問題ですが、DNAシークエンシングの広く知れ渡ったものです。
リファレンスが使え、すべてのリードは、リファレンスDNAのきっちりとしたポジションに結び付けられることが期待されます。
We seek an algorithm that not only aligns each read quickly and correctly, but also accurately estimates the ambiguity of each match if alternative matching positions are available.
私たちは、それぞれのリードが素早くかつ正確にアラインされるだけでなく、あやふやなマッチを正確に評価できるアルゴリズムを探しています。
Background (Biology 101)
背景（生物学入門）
A molecule of double stranded DNA can be thought of as two strings of identical length each consisting of four characters — A, C, G, or T. These two strings are reverse complementary: substitute A for T, C for G, G for C, and T for A in one of the strings, reverse the result, and you obtain the other string. The two strings are bound to each other such that each character is always adjacent to its complement:
二重らせんDNA分子は、４つの文字で構成される同じ長さの２つの文字列(A, C, G, T)で考えることができます。
これらの２つの文字列は、相補的です。
文字列中で、Aに対してはT, C => G, G => C, T=> A といった感じです。反対にする感じですね。
２つの文字列はこんな感じで相補的な文字と隣り合う形になります。
Thus, double stranded DNA sequences are discussed with respect to only one of the two strings, since it is trivial to obtain the other via reverse complement.
このように、相手方は相補的で自明なので、２つの螺旋状DNAシーケンスは、２つの文字列のうちの１つを取り上げて議論されます。
Every somatic human cell contains two copies of the individual’s genome, inherited from the mother and father. A copy comprises 23 separate molecules of double stranded DNA called chromatids. The length of a single string from each chromatid ranges from ~250 million to ~45 million characters, summing to a total length of approximately 3.2 billion characters:
すべての人間の細胞は、お父さんとお母さんから受け継いだ、２つの遺伝子のコピーを持っています。
各コピーは、染色体と呼ばれる23個のらせん状DNA分子で構成されています。
それぞれの染色体の文字列は、2億5千万文字くらいのものから、4500万文字のものまで、幅を持っています。
合計すると、だいたい32億文字くらいです。
The two copies differ only by approximately 0.5%, so it is often not necessary to consider each copy as a totally separate entity. Indeed, this 0.5% difference holds on the population level as well — two unrelated people can expect their genomes will be 99.5% identical. This lets us assemble a reference genome: a universal set of chromatid sequences constructed from several people, designed to closely approximate the human species as a whole. An individual’s genome can therefore be characterized strictly by its differences from this reference.
２つのコピーは、たったの0.5%くらいしか違いがありませんので、
それぞれのコピーは別物と考える必要はないと言ってよいでしょう。
実際には、この0.5%の違いは、人口レベルの単位では維持されています。
二人の他人の99.5%の遺伝子は同じになるでしょう。
この事実により、私たちは以下のようなリファレンスとなる遺伝子を組むことができます。
* 複数の人からくみ上げた一般的な染色体シーケンス
* 人類の近似値としてデザインされている
To elucidate these differences, however, we still must sequence every character in an individual, since we do not know a priori where the differences will arise.
しかし、我々は、この違いがどこからくるのか分かっていないので、
(0.5%の）この違いをはっきりさせるためには、個別のすべての文字を吟味する必要があります。
Unfortunately, current technology does not allow us to directly read each chromatid in a single pass. Instead, we must extract the individual chromatids from several million cells in a tissue sample, and fragment these long double stranded DNA molecules into shorter double stranded fragments, each about 600 characters long (normally distributed). The 150 characters from both ends of each fragment can be directly sequenced, forming paired end reads. The strands can be read only in one direction, reversely oriented for two strands. Thus the reads for a read pair always come from opposite strands:
残念ながら、今日のテクノロジでは、直接それぞれの染色体を一度に読み取ることはできません。
代わりに、組織片に含まれる数百万個の細胞から得られる個々の染色体を取り出さなくてはなりません。そして、これらの長大な２重らせんDNA分子をより短い２重らせんの切片、それぞれだいたい600文字長に切り分けます。
それぞれの切片の両端から150文字、ペアの末端リードは、直接読み取ることができます。
この鎖は、一方向からのみ読むことができ、２つの鎖に対して、反対の方向性を持ちます。
このようにリードのペアは、常に反対側のDNA鎖からなります。
We then do one of two things:
次に我々は対となる２つのことの一方を行います。
Reassemble these reads into a complete chromatid, a process called de novo assembly. This is akin to reconstructing a shredded document, or assembling a jigsaw puzzle without knowing anything about what it will look like. This process is extremely time-intensive, since there can be billions of reads, and each must be compared to every other. This is how reference genomes are first constructed for a species.
これらのリードを完全な染色体に再構成します。これははじめからの組み立てと呼ばれるプロセスです。
これは、シュレッダーに掛けた文書の再構築や、ジグソーパズルを、完成時にどう見えるかといった知識なしに組み上げることと似ています。
このプロセスは、数十億個のリードがあって、それぞれを互いに比較しなければならないので、究極的に時間がかかります。
これは、最初に種に対してリファレンスとなる遺伝子の作り方です。
Align these reads with respect to a reference genome. Since no two human genomes differ by more than 0.5%, we can expect most reads will be exact or near-exact matches to corresponding substrings in the reference. This process is called alignment:
リードをリファレンス遺伝子に対して、整列させます。
二人の人間の遺伝子は、0.5%も違わないので、ほとんどのリードは、正確にまたはほぼ正確にリファレンスの部分文字列に対応させることが期待できます。
このプロセスは、アラインメントと呼ばれています。
and is orders of magnitude faster: if we construct a suffix tree on the reference, exact substring matching of a read of length n can be done in O(n) time. This is akin to assembling a jigsaw puzzle using the picture on the box as an aid.
そして、桁違いに早く処理できます。リファレンス上に接尾辞木を作った場合、長さnのリードに対する正確な部分マッチは、O(n)時間で見つけることができます。
これはジグソーパズルを箱に書いてある絵を頼りに組み上げることと似ています。
This challenge will focus on the second approach: alignment, since it is currently the most widely used approach to sequence individual genomes.
今回のチャレンジは、この２番目のアプローチであるアラインメントに焦点を当てます。
それは、現在、個体の遺伝子を順番に並べるためにもっとも広く使われているアプローチです。
Objective
目的
There are two major challenges within the alignment problem that we hope you will address in this competition:
今回のコンペティションでは、あなたがたに解決してほしい、アラインメント問題の中の２つの大きなチャレンジがあります。
A Read May Not Perfectly Match the Reference. A fraction of the reads will have no exact substring match in the reference due to genetic variation and sequencing errors.
！！！リードは、リファレンスに完全には一致しません！！！
リードのいくらかの部分は、遺伝的変異やシーケンスエラーのため、リファレンスに正確にマッチしません。
Although it is possible to obtain the exact alignment of two strings via the Smith-Waterman or Needleman-Wunsch algorithms, this procedure runs in time proportional to the product of the strings’ lengths; in theory, this could be done for every read, but would be computationally infeasible.
２つの文字列の完全なアラインメントは、Smith-Watermanアルゴリズム や Needleman-Wunschアルゴリズムを通して得ることができますが、この処理は、文字列同士の長さの積に比例した時間(O(n^2)？)が掛かり、理論的にはすべてのリードに対して行うことができますが、計算量的に実現不可能です。
There is no known efficient solution to inexact substring matching.
不正確な部分文字列マッチングに対する効率的な解法は知られていません。
Matching May Be Ambiguous. Portions of the genome are highly repetitive — in extreme cases, thousands of characters may be repeated thousands of times. It is impossible for 150 character reads to unambiguously map to these regions, but it is very important to know that the reported match may not be accurate.
！！！マッチ処理は、あいまいなものになるかもしれません！！！
遺伝子の一部分は、高い可能性で繰り返します。極端な例では、数千文字が、数千回繰り返される場合があります。
１５０文字のリードを曖昧性なくこれらの領域にマップすることは不可能です。
しかし、報告されたマッチ結果が不正確かもしれないということを知ることは大変重要です。
The aligner must accurately measure the ambiguity of each mapping and report it via a mapping confidence score.
アラインメントプログラムは、正確にマッピングの曖昧性を測定し、マッピング確度スコアによってそれを報告するものでなければなりません。
Data Description
データの説明
For training, contestants will be provided with:
訓練データとして、参加者には以下のデータが用意されています。
Reference genome. This consists of 24 text files (in FASTA format) containing one string per chromatid sequence, totalling ~3.2 billion characters. As noted previously, this does not include the genomic reverse complement; however, the simulated reads will come from both strands. The reference contains some unknown sequences, which are masked by the character N; we will not be simulating reads from these regions.
「リファレンス遺伝子」
これはFASTAフォーマットの24個のテキストファイルで構成されています。
染色体シーケンスごとに１つの文字列を持たせており、合計で32億文字くらいになります。
以前に注記したように、これには逆相補配列を含めていません。
しかし、シミュレーションで生成したリードは、両方の鎖を持つようにしています。
リファレンス遺伝子は、いくつかの不明なシーケンスを含んでおり、それらは、'N'でマスクされていますが、この領域にマッチするリードは今回含めていません。
Simulated reads. Sequences will be extracted randomly from the genome and will contain deviations from the reference according to empirically observed genomic variants and sequencing error rates. These will be also be provided in the FASTA format, which provides the 150 characters for each read. The read pairs will be split across two matched order FASTA files, i.e. all the first-of-pair reads will be in the first file (.fa1) and all the second-of-pair reads will be in the second file (.fa2).
「シミュレーション生成したリード」
シーケンスは、遺伝子からランダムに取り出し、経験的に観測されている変異率、シーケンスエラー率を参照して変化させています。
これらのデータもFASTAフォーマットでそれぞれのリードは150文字で提供されます。
このリードのペアは２つの順序が一致したFASTAファイルに分離されます。
ペアの最初のリードは、最初のファイル(.fa1)、２番目のリードは、次のファイル(.fa2)です。
Ground truth. The correct mapping of each read will be given in a ground truth table. The format of this table is as follows:
ReadName ChromatidSequenceId Start position End position strand (reference [+] or reverse complement [-]) read string i.e.
sim1/1 1 10000 10149 + ACGTACGGATATACGATAGGACAGT...
sim1/2 1 10500 10652 - CGATACGAGTTAGACACAGATTATA...
Read names will be identical to their counterparts in the FASTA files.
「グラウンドトゥルース」
それぞれのリードの正解マッピングは、グラウンドトゥルース表で与えられます。
この表のフォーマットは以下の通りです。
| リード名 | 染色体シーケンスID | 開始位置 | 終了位置 | DNA鎖(リファレンス [+], 逆相補 [-]) | リード |
|---|---|---|---|---|---|
| sim1/1 | 1 | 10000 | 10149 | + | ACGTACGGATATACGATAGGACAGT... |
| sim1/2 | 1 | 10500 | 10652 | - | CGATACGAGTTAGACACAGATTATA... |
リード名は、FASTAファイルに対して同一です。
For the competition, submissions will be provided with the same reference genome and new sets of simulated reads. Each submission will undergo up to three competition tests with increasing difficulty, with access to more difficult tests contingent on adequate performance on easier tests. The tests differ in complexity by the number of reads to be aligned and the number of chromatids the reads are to be aligned to.
このコンペでは、提出物には、同じリファレンス遺伝子と新たに生成されたリードが用意されます。
各提出は、段階的な難易度を持つ３つまでのコンペテストに対峙することになります。より難易度が高いテストは、簡単な方で十分なパフォーマンスを達成した場合に行われます。
テストの難易度は、配列するリードの数とリードが配列される染色体の数で決められています。
Small test: Chromosome 20 (~64 million characters in human reference hg38), up to 10 thousand read pairs
スモールテスト
２０番染色体(6400万文字), １万個までのリードペア
Medium test: Chromosomes 1, 11, 20 (~450 million characters), up to 1 million read pairs
ミディアムテスト
１番、１１番、２０番染色体(4億5000万文字）, 100万個までのリードペア
Large test: Entire genome — 24 chromatids (~3.2 billion characters), up to 10 million read pairs
ラージテスト
24個すべての染色体(32億文字）、1000万個までのリードペア
Functions
関数群
The example and provisional test case will contain two tests with different difficulty (small, medium) while the system test case will contain three tests (small, medium, large). The DNASequencing class won’t be reinstantiated between the small and medium tests. For the large system test, solutions will be run stand-alone outside of the normal submission system on VMs with similar characteristics to the test processors.
例題、仮テストケースは、スモール、ミディアムの難易度が異なるテストを含みます。これに対して、システムテストケースは、スモール、ミディアム、ラージの３つのテストケースを含みます。
DNASequencing クラスは、スモール、ミディアムテスト間で再インスタンス化しません。
ラージシステムテストに対しては、プログラムは通常の提出システムの外にあるテストプロセッサと同じ特徴を持つVM上で、スタンドアロンで実行されます。
This set of functions will be called at most 2 times from smaller test to bigger ones. For large system tests, it will only be called once.Functions call order for a test within a testcase as follows:
以下の関数群は、テストの大小にかかわらず高々２回呼ばれます。
ラージシステムテストに対しては、１回のみ呼ばれます。
テストで呼ばれる関数呼び出しの順穂は、以下の順になります。
1. -- Preprocessing time limit starts counting here
2. int initTest(int testDifficulty)
testDifficulty can be 0 - small, 1 - medium, 2 - large. Return can be any valid integer.
3. int passReferenceGenome(int chromatidSequenceId, string[] chromatidSequence)
Will be called 1, 3, or 24 times according to the test difficulty. Return can be any valid integer.
4. int preProcessing()
Return can be any valid integer.
5. -- Preprocessing time limit ends here
-- Time Cutoff starts counting here (the time used for scoring)
6. string[] getAlignment(int N, double normA, double normS, string[] readName, string[] readSequence)
Will be called once per test size.
N is the number of reads in the test.
Both array will contain exactly N elements as well as the return array. Elements at (2*i) and (2*i+1) are representing a read pair.
Format of the return string:
ReadName, ChromatidSequenceId, Start position (1-based), End position (1-based), strand (reference [+] or reverse complement [-]), mapping confidence score
“sim1/1,1,10000,10149,+,0.89”
“sim1/2,1,10500,10652,-,0.82”
“sim2/1,1,11500,11649,-,0.75”
“sim2/2,1,11300,11449,+,0.63”
7. -- Time Cutoff ends here
Data generation
データ生成
Data Overview: All the reads in the data have their positions mapped to the reference. The absolute majority of the reads will also have very good to perfect alignment with the reference. Some overlaps with large deletions may occur and have to be taken into account.
データの概要
データに含まれるすべてのリードは、リファレンスDNA上のポジションを持っています。
ほとんどのリードは、リファレンスに対して、完全に一致します。
大量の削除に伴う重複が発生することがあり（？）、考慮しておく必要があります。
Simulated reads: We simulated true genomic variants and sequencing errors according to their actual observed frequencies:
シミュレーション生成されたリード
実際に観測された頻度で、遺伝的な変異や読み取りエラーをシミュレートします。
True variants: Single character substitutions occur every ~1/800 bases. Insertions and deletions occur with cumulative frequency of ~1/5000 bases; relative probability of insertion or deletion is equal to inverse length of insertion or deletion. The insertions are limited to a length of 40 and deletions to a length of 200.
変異
１文字の入れ替わりは、それぞれの文字において1/800くらいの確率で発生します。
挿入と欠落は、累積確率で、1/5000くらいです。挿入と欠落の相対的な確率は、挿入または欠落の長さの逆数になります。
挿入長は、最大40文字、欠落長は最大200文字です。
Sequencing errors: Single character substitutions occur every ~1/500 bases. Erroneous insertions and deletions occur every ~1/1000 bases. It is rare to see an erroneous insertion/deletion of more than two characters; the vast majority are one character.
シーケンスエラー
１文字の入れ替わりは、それぞれの文字において1/500くらいの確率で発生します。
挿入、欠落エラーの発生確率は、それぞれの文字において1/1000程度です。
２文字以上の挿入または欠落は、ほぼ発生しません。ほぼすべての挿入・欠落は１文字です。