バイオインフォマティクスのアルゴリズムの問​​題。 Yandexでの講義

データアナリストと科学者がお互いにタスクについて話し合い、相互作用する方法を探すイベントのデータ＆サイエンスシリーズについては既に何度か言及しました。 会議の1つはバイオインフォマティクスに捧げられました。 これは、開発者にとって未解決のタスクがたくさんある業界の素晴らしい例です。







カットの下には、モスクワ州立大学の力学学部とデータ分析学部の卒業生であるイグナット・コレスニチェンコによる講義の写しがあります。 Ignatは現在、Yandexの分散コンピューティングテクノロジーサービスの主要な開発者です。

---

ここのプログラマは誰ですか？ 聴衆の約半分。 私のレポートはあなたのためです。



レポートの目的は次のとおりです。データの取得方法と配置方法を正確に説明します。 物語はアンドレイの物語より少し深くなるでしょう。 これを行うには、生物学について少し思い出させる必要があります。 少なくともプログラマーが生物学を知らないことを願っています。



そして、この分野でどのアルゴリズム的に複雑な問題が解決されているのか興味を持たせるために、それが素晴らしいことを理解し、バイオインフォマティクスに取り組み、人々が複雑な問題を解決するのを助ける必要があることを伝えようとします。 明らかに、生物学者自身がアルゴリズムの問​​題に対処することはできません。



mehmatを卒業しました。 私は数学者で、Yandexで働いています。 私はプログラマーであり、YTシステムに取り組んでおり 、Yandexで内部インフラストラクチャを行っています。数千台のマシン用のクラスターがあります。 Yandexが収集するすべてのデータはこれらのクラスターに格納され、すべてが処理されます（ペタバイトのデータ）。これについては少し理解しています。 私はエビノムの共同創立者でもあります。 そこで私は同じ技術的な仕事に従事していました。 私の目標は、これらのアルゴリズムとプログラムがどのように機能するかを理解し、それを最も自動的に行う方法を教えることで、ユーザーがウェブサイトにデータをアップロードし、ボタンを押すと、クラスターが展開され、すべてが迅速に計算され、最小化され、データが人には思えたでしょう。



この技術的な問題を解決している間、問題のデータとその処理方法を把握する必要がありました。 今日は、学んだことの一部を説明します。



Gelfandのビデオは 、このイベントの発表でFacebookに投稿されました。 誰が見ましたか？ 一人。 ゲルファンドはあなたを不満に見ています。







私たちはDNAを使って作業しますが、DNAについて少しコンテキストが欲しいので、細胞から始めます。 分子生物学の科学としてのバイオインフォマティクスが細胞内のすべてのプロセスに関心を持っていることは明らかですが、本日は技術面、データについてさらに詳しくお話しします。もちろん、コアおよび近くのコンポーネントのみに関心があります。



コアにはDNAが含まれています。 核小体があります。 アンドレイが示したヒストンとともに、それはある意味で規制とエピジェネティクスの原因となっています。 2番目の重要な部分があります-リボソーム、核の周りの折り畳み、いわゆる小胞体。 リボソームと呼ばれる分子の特別な複合体があります。 タンパク質を作るために最初にDNAから差し引くDNAの断片からになります。



3番目の部分はクロマチンです。すべてのDNAが浮遊しているすべての物質が見つかります。 ぎっしり詰まっていますが、それでも多くの異なる調節分子があります。 まあ、膜があります-保護、栄養、細胞が通信する方法。



セルには他にも多くの機能があります。 それらについては話しません。教科書で読むことができます。







次に、情報、DNA、およびRNAについて説明します。 2つの主要な分子があります：デオキシリボ核酸およびリボ核酸。 これらは同じタイプの分子です。 ワトソンとマックリックはかつてこの分子の構造を発見しました。 面白い話、自伝を読むことができます、彼はすべてについて非常に美しく書きます。 それは二重らせんであり、人気のある絵、人気のある流行語です。



それは4つの大きな分子、数十個の原子の複合体で構成されています。 これらはグアニン、シトシン、アデニンおよびチミンです。 さらに、チミンの代わりにRNAではウラシルになります。 DNAからRNAを作成すると、「T」の代わりに「U」の文字が表示されます。 私たちの4つの文字がDNAに含まれていることを知ることは重要です。 私たちは概して彼らと一緒に仕事をします。



DNAはより高い構造を持っています。 これは単なるスパイラルではなく、何らかの形で存在しています。 ヒストンという特別な複合体の周りを渦巻いています。 次に、ヒストンがいくつかの繊維にねじれ、そこから文字Xがすでに構築されています。これは、生物学の教科書で見た美しい写真です。 通常、彼らはヒストンについて話さない、彼らは15年前には言わなかったが、彼らは文字Hを示す。それはそのように配置され、DNAはそこにunningな方法でねじれている。



ヒストンは規制に責任があります。 DNAを使ってある種のRNAを読みたいと思うと、うまくいかないかもしれません。 あるいは、何かが変化して、読み始められるかもしれません。



そして、これらすべてに取り付ける方法を知っているリス、それを広げる方法を知っている、あなたが読むためにそれを引き出すリスがあります。 二次構造は、DNAのどの部分からRNAタンパク質を作成できるかを理解するために非常に重要です。







タンパク質とは何ですか？ 細胞の主な活力、すべての生物の多様性は、主にタンパク質に起因しています。 事実、タンパク質には非常に高い変動性があります。 これは、巨大な分子の山に参加する非常に多様な分子の巨大なクラスです。 それらは非常に異なる構造を持っているため、この複雑な化学反応はすべて細胞内で起こります。



タンパク質について知っておくべきことは何ですか？ 化合物ブロックはアミノ酸です。 私たちの体内のアミノ酸、私たちの世界では20個。 彼らはもう少しいると言いますが、私たちの体には20があります。彼らは特定のラテン文字も持っています。 タンパク質は右に模式的に描かれ、その始まりが書き出され、どの文字が存在するかが示されます。 私は生物学者ではありません。VまたはMが何であるか覚えていません。生物学者は文字の意味をすぐに言うことができます。



タンパク質の構造にはいくつかのレベルがあり、単純にシーケンスとして見ることができます。バイオインフォマティクスの場合、多くの場合はそのように見えます。 アーサーはより複雑な二次および三次構造に関心がありますが。



これを一連の文字と見なします。 二次および三次構造。 そのようならせん、アルファらせんがあり、それらは写真ではっきりと見えます。 ベータシートもあり、かなり平らな部分に並べる方法を知っています。これらのアルファスパイラルとベータシートを収集する特別な部分があります。







さらに、アンドレイが言ったことは、分子生物学の中心的な教義です。 それは、翻訳と転写があり、RNA、DNA、およびタンパク質が異なる方向に関与する、より多くの異なる逆プロセス、垂直があるという事実にあります。 しかし、今日は放送と文字起こしのみを見ていきます。 右側には、真核生物の細胞、特にヒトにおけるこのことを説明するかなり完全な図があります。



遺伝子はありますか？ 生物学の教科書では、これは遺伝の単位であると書いています。 私たちにとって、DNAを見ると、遺伝子はそれほど単純ではないサイトです。 pHに変換されるわけではありませんが、タンパク質はRNAから作られます。 すべてが少し間違っています。 まず、このセクションには、切り取られた領域、イントロンがあります。 また、後でタンパク質にエンコードされるエクソンがあります。 DNAを30億文字で見ると、これは一般的なフレーズです-重要な領域は2％しかありません。 遺伝子のコーディングを担当しているのはわずか2％です。 そして、我々はエクソンについて話している。



より多くのイントロンを取得すると、2％ではなく20％が得られます。 そして残りの80％は遺伝子間領域であり、明らかにある程度規制に参加しています。 しかし、歴史的にそうであるように、いくつかは本当に必要ありません。



次のことが起こります。遺伝子の前に特定のプロモーターがあり、このプロモーターの上に特別な分子があります。これは、DNAからRNAを読み取ってRNAを生成するタンパク質です。



さらにRNAから、変換は別の分子によって行われ、それにより不必要なイントロンが切り取られます。 既製のメッセンジャーRNAを取得して、そこからタンパク質をブロードキャストします。 この場合、「3」および「5」は切り取られます-エンコードされていない端。 RNAからタンパク質を作るとき、実際にはトリプレットがあり、いくつかのシーケンスを開始できます。 彼女の前のすべては単にスキップされます。 細胞は座って、これをスキップし、開始コドンからすべてを始めます。



私はコドンという言葉を使いました。 コドンとは何ですか？ エンコードはどのように機能しますか？ ロジックは簡単です。 DNAには、A、C、T、Gの4つの文字があります。タンパク質には20の文字、20のアミノ酸があります。 4つのうち20を作成する必要がありますが、これが直接機能しないことは明らかであり、何らかの方法でエンコードする必要があります。 コーディングに携わっている科学者の観点から見ると、このデバイスは非常にシンプルで愚かなコーディングであり、簡単に考え出すことができます。 しかし、生物学の観点から、これを達成することは容易ではありませんでした。



3文字のDNAが読み取られており、各文字の3つ組は特定のアミノ酸をエンコードしています。 文字64のトリプレットと20個のアミノ酸を64個のバリアントにエンコードできます。 エンコードは冗長です。 同じものをエンコードするさまざまなトリプレットがあります。



放送と文字起こしについて今日知っておく必要があるのはこれだけです。



アンドレイは、メタゲノミクス、さまざまなオーミックについて多くのことを話しました。 過去50〜100年の科学者は、生物学だけでなく、細胞内で何が起こっているのか、どのプロセスがあり、どのような化学が存在するのかを非常に積極的に研究しています。 そして、彼らはこの問題で非常にうまくいった。 彼らは完全な絵と理解を持っていないかもしれませんが、多くのことを知っています。



異なる物質の相互変換の大きな地図があります。 特に、ほとんどの要素はタンパク質であり、一般的に細胞内で起こることを記述しています。







ここに小さな断片がありますが、大きな絵があり、科学者はそれを描くのが好きです。 私たちの前にあるのは、セルで行われるすべての概略的な簡略化されたスキームです。



すべての分子は多かれ少なかれ常に細胞内に存在することを理解することが重要です-問題は濃度にあります。 常に、どこかでDNAが展開し、そこから何かが読み取られます。読み取られるものは、さまざまなタンパク質の濃度に大きく依存します。 そして、細胞の生涯は規制です。 あなたはもっと大きくなり、何かが他のプロセスよりも大きくなり、彼は何かをもっと放送し始め、新しいタンパク質が現れ、彼は何らかのプロセスに参加し、私を生産するのに十分だと言って、彼は新しいタンパク質を生みました。その生産に干渉し始めました。 このようなフィードバックループプロセスは、セル内に多数存在し、一般的にここに表示されます。



これらのA、C、T、Gからデータはどこから来ますか？ アンドレイは、あなたにそれらを読むシーケンサーがあると言いました。 これらのデバイスがどのように配置され、何を読んでいるのかをさらに詳しく理解しましょう。



70年代後半に発明され、1989年にプロジェクト「Human Genome」を開始できる古典的なサンガー法があります。 2001年までにプロジェクトは完了し、30億文字の「参照」者のシーケンスを組み立てることができました。 23個の染色体すべてを分析し、各染色体にA、C、T、Gの文字が何であるかを認識しました。



Sengerの方法は良好で信頼性が高く、科学者は彼を信頼していますが、彼は非常に遅いです。 1977年、それは恐ろしい恐怖でした。あなたは放射性溶液と手袋の物質で作業し、鉛の小さなものの後ろにいて、試験管のどこかに何かを注ぎました。 これらの演習の3時間後、誤って間違った場所に何かを注がなかった場合、200ヌクレオチドのDNAを認識できる写真が得られます。



プロセスが迅速に自動化されたことは明らかであり、自動化の過程でテクノロジーが少し変化しました。 2000年代半ばまでには、400文字ごとに高価な科学者の3時間の作業を費やすことなく、シーケンスを迅速かつ安価に実行できる新しいテクノロジーが多数登場しました。



アンドレイが最後に語った技術は、ミニナノポアです。 科学界では、この技術が主流になるかどうかについてまだ疑問があるように思えます。 しかし、それは確かに私たちにとって新しい境界線を開きます。



以前の技術はすべてかなり正確であると考えられており、エラーはほとんどありません。割合と割合について説明しています。 このテクノロジーには10〜20％の大幅なエラーがありますが、大きなアイデアを読むことができます。 大規模なアプリケーションでは、これは本当に必要なようです。



エラーも少ないテクノロジーに仕上げることができるかどうかは不明です。 しかし、可能であれば、それは非常にクールです。



シーケンス処理、これがどのように行われるかについての全体像。 彼らはあなたからサンプルを採取し、血液検査、唾液の分析、または特別なピンセットで登り、骨髄の断片を取得します。非常に痛みを伴う怖い手順です。 さらにサンプルに沿って、いくつかの化学反応が行われます。これにより、不要なすべてが削除され、サンプルに存在するDNAのみが条件付きで残されます。



次に、DNA断片化を行い、小さな断片を取得してさらに伝播し、より多くの断片が存在するようにします。 これは多くのテクノロジーで必要です。 次に、シーケンサーにデータを送信し、何らかの方法ですべてを読み取ります。



出力は常に同じfastqファイルです。 すべてのデバイスはさまざまな方法で動作し、長さもエラーの種類も異なります。このデータを使用する場合は、エラーの種類、そのようなデータを正しく処理する方法を理解することが重要です。 すべてに同じメソッドを適用すると、信頼できないダーティデータが得られます。



Sengerメソッドについて簡単に説明します。 アイデアはとても美しいです。 DNA配列があり、それを繁殖させて、試験管に浮かせます。 次に、それが何で構成されているかを理解します。 そこには特別なリスが食べられます。 おそらくすべてのDNAがそこに浮かぶこともありますが、それを分解する方法を知っている分子も浮くでしょう。



科学者には非常に簡単な方法があります。 彼らはどのようにしてDNAを使ってそのようなことをすることを学びましたか？ 彼らは、自然がどのように細胞内で同じことをしているのかを見て、自分たちがしているタンパク質を理解し、それらを手に入れて、今やDNAを複製できるようになりました。 複製に関与するタンパク質を取り、それらを試験管に入れるだけです。 そこにすべてが起こります。



彼らはこれらのリスを投げ、そして私たちのACTGも投げます。 その中には、特別なものがマークされており、読み取り時にDNAに接着されると、それ以上接着できなくなります。 このすべてを投げ、揺さぶり、しばらく放置すると、興味のある未読の元のDNAの断片が得られます。 私たちはランダムに何かを貼り付けますが、希望は長さごとに何かが貼り付けられることです。この瞬間に停止するTTRが貼り付けられ、すべてが停止します。



より特別なタグ付きACTG、蛍光。 特別な方法でそれらを照らすと、それらは緑、青、赤、または黄色になります。 次に、これらすべてがゲルに投げ込まれ、そこで質量で分配され、強調表示され、右のように写真が撮られます。 さらに下から上に向かってカウントすることができます：短く、高く、低くなります。







その結果、fastqファイルを取得します。 外観は右側に描かれています。 これは、プログラマがすでに困惑しているはずのテキスト形式です。圧縮できるのに、なぜテキスト形式で保存するのですか？ それで起こった。 実際、それらはそのようなファイルに保存されており、KZIPでそれを押すだけです。 ファイルには4行のデータが含まれます。最初に、読み取り、読み取りの1つのIDが来ます。 そこで読まれた手紙。 それからいくつかの技術的なライン、そして4番目のラインは品質です。 すべてのデバイスは、読み物にどれだけ自信があるかの指標を提供できます。 さらに、データを操作するときは、これを考慮する必要があります。



ほとんどのアルゴリズムの本質は、ランダムな断片を何度も何度も読み取り、大きなカバレッジで読み取ることです。 次に、元のDNAがどのように見えるかを理解する必要があります。 人々がヒトゲノムプロジェクトを始めたとき、彼らは実際に他の組み立てられたゲノムを持っていなかったことは明らかです。 バクテリアはそれからすでに収集することを学びました。 そして、それはひどい仕事でした。 あなたは人間のゲノムを持っています、それは30億文字を持っています。 長さ300から400の断片を手に入れたので、今度はそのような断片がどのシーケンスから得られたのかを理解する必要があります。 怖いですね。



アルゴリズムについて話しましょう。 NGSを使用してどのような問題が解決され、アルゴリズムの観点からどのように解決されますか？







最初のタスクは、ゲノムの組み立てです。 それについて、あなたは6ヶ月の講義コースを読むことができます、多くの資料があります。 ここでどのアルゴリズムが使用されているのか、なぜ難しくて興味深いのかを理解できるように、一般的なアイデアのみを概説します。



ゲノムアセンブリのタスクは何ですか？ リードはfastq形式で提供され、数百万または数千万があります。 たとえば、1つの染色体を収集します。 そして、収集したいゲノムまたは染色体を取得する必要があります。



さて、プログラマーの観点から、このタスクはどのように定式化されますか？ ACTG文字の短い文字列があり、品質、重量のいくつかの指標があります。 そして、それらを収集するとき、答えにはまだ制限があります。 生物学者がヒトゲノムを収集したとき、彼らは11番目の染色体上にそのような遺伝子が存在することを知っていました。長い研究の結果、それらを調べ、他の方法でそれらが存在することがわかりました。 そして、私はこれを考慮に入れたいです。 何かを収集してからそれを見つけるのは愚かなことでしょう-アルゴリズムがそう決定したので、私たちが確信していることのために、何らかの理由でありません。



すべての短い行にわたって何らかのスーパーラインを取得する必要があります。 そして、できるだけ小さくしたいと考えています。 それ以外の場合は、すべてのフラグメントを簡単に貼り付けて、誰にも合わないものを取得できます。 すべての入力ラインは染色体から取得されているため、この染色体を見つける必要があることを意味します。 十分に大きなカバレッジでこれを行った場合-条件付きで、各シフトにいくつかの線があります-そして最短のものを収集し、これが私たちのゲノムになります。 上記は常に真実であるとは限らず、そのような処方で何かを失うか見逃すことができるさまざまな理由があります。 しかし、これはすべての人に適した十分な近似値です。







タスクの簡略化された例。 長さ16よりも短いスーパーストリングをまとめると、次のようになります。 CCTAの最後の行に最後から2番目の行を貼り付け、それらからの文字TAが重なりました。 したがって、2つの文字を保存しました。 その後、最初の行をスピーカーに接着しました。 TGAC , . , . .



. , , , NP-. , , : . : , - ? 2 10 — .



しかし、良いニュースがあります。 , - . .



: . . , , , .



, , . 100 . , , . , , scaffold'. , .



. 80- 90-, , . 60- 70-, . , . -, , . , 80- , . , . .



? Overlap-Layout-Consensus. overlay-, , , , .



Overlay- — . , — — , .







. 5, , .



, , . , , — . , overlap. , . , , , , . , .



1990 , , , . . , , overlay . , — . . overlay, .



, . , , . . , overlay.



, , , 100 1000. , , , .



, . . , , , . , . , , , .



, . , , , . , , . overlay , , , .



- . , .



. , 1989 . -, , , -, .



: , . , , , , . , .



, , . , k = 4, , , k= 4, , . - , . , , — , - - , - . .



— .



, k . , k = 2, , .



, , , , . , , .



. : , . . : , . - .



: , , , . , . , , .



, . . , , , , . , .



, . — , , , , . , , , . , .



, , , . : , . — . - , . , , . , , , , . . . , , , .



, , — . , , , , . , , .







. , . , .



? . , , , … , , . , , .







, , — . ? , . , . , , . . , , . , , . , . , .



, , - , , . , - , . , , , . , , - , - . - . .



: -, , -, . 10 . — - . , , , , , . .



machine learning. , , , .



.







. , , — . , , , , , , . - - , , , , , . - , , , , , . - , . , , , , .



, , - , . , . , , , . , , , - . . , : , — . . . .



. , , ? - , , , . , , , , , , . — , , , : , .



, . , , , -. . , , . , , , , .



, , , . , . , : , , , , , , . -, , , . -, , , . , - , , , , . , , , . , . , , .



結論として、バイオインフォマティクスを学びたい場合は、講義を視聴して何かを読むことができます。または、専門の機関、たとえば、コンピュータサイエンス学部の経済学部などに留学することもできます。2016年には、全体としてバイオインフォマティクスの修士課程が一般にオープンしました。「生物学と医学におけるデータ分析」と呼ばれますが、コースを開くと、一般的にはバイオインフォマティクスになります。



また、バイオインフォマティクススクールもあります。これもFBBと一緒にやっています。サンクトペテルブルクにバイオインフォマティクス研究所があります。一般に、多くの異なるオプションがあります。どうもありがとう。