Сборка генома - это вычислительный процесс, в котором определяется последовательность нуклеотидов составляющих геном организма. В настоящее время иследователи не могут прочитать последовательность нуклеотидов всей хромосомы. Вместо этого, они полагаются на высокотехнологичные химические методы, чтобы определить порядок нуклеобаз вдоль некой короткой части нити ДНК. Короткие фрагменты, полученные в результате, называются "reads".
Чтобы опеределить геном, исследователи проводят данную химическую операцию несколько раз над несколькими копиями одного и того же генома, каждый раз получая некоторую короткую последовательность какой-то его части. Чтобы "собрать геном", они должны использовать пересечения в полученных строчках, чтобы понять какие последовательности примыкают друг к другу. Например, получив две короткие последовательности GGTGACC и ACCTCGA, они могут заключить, что они обе относятся к подстроке GGTGACCTCGA.
В общем случае неизвестно, каким образом пересекаются полученные фрагменты. К тому же, в ДНК две комплементарные нити и мы не знаем, с какой из них получен тот или иной фрагмент, и должны ли мы использовать его или его комплементарное отражение. Некоторую сложность привносит то, что современные методы чтения не идеальны и зачастую содержат ошибки. Также, некоторые регионы генома могут быть совсем не покрыты фрагментами. Однако, в нашей задаче мы возьмем упрощенный идеальный случай: мы будем считать, что наши фрагменты не содержат ошибок, получены с одной и той же нити ДНК, а также полностью покрывают геном. Причем мы точно знаем, размер пересекающихся частей фрагментов и то, что он одинаков для всех фрагментов.
Разработать функцию, принимающую в качестве аргументов набор N строк одинаковой длины D в произвольном порядке, полученных в результате чтения, и натуральное число K (K < D) - длину пересекающихся концов фрагментов, возвращающую одну строку - геном, собранный из всех фрагментов. Гарантируется, что для всех входных данных такая строка существует и при том только одна.
std::string assemble(size_t k, const std::vector<std::string> & fragments);Необходимо решить данную задачу, разбив входные фрагменты на все возможные подстроки размером (k + 1). Каждая такая подстрока будет соответсвовать переходу в направленном графе, где первой вершиной будет префикс размера k подстроки, а второй - суффикс размера k этой же подстроки. Например, для фрагмента ATCG и k = 2, подстроками будут ATC и TCG. Из первой подстроки получим две вершины и ребро: (AT) -> (TC), из второй: (TC) -> (CG). Повторив операцию для каждого исходного фрагмента, получим набор вершин и ребер. Склеив одинаковые вершины (но не склеивая ребра!), получим направленный граф, в котором присутсвует Эйлеров путь. Найдя этот путь, мы получим искомую строку - геном.
Возьмем входные данные из первого примера ниже.
K=2, [AATCT, ACGAA, GCTAC]
-
Разобьем первый фрагмент на все возможные подстроки размером k + 1: AATCT -> AAT, ATC, TCT;
-
Проделаем то же самое с остальными фрагментами: ACGAA -> ACG, CGA, GAA; GCTAC -> GCT, GTA, TAC;
-
Каждая из полученных маленьких строк представляет собой переход в графе с вершинами из подстрок размером k.
AAT: (AA) -> (AT);
ATC: (AT) -> (TC);
TCT: (TC) -> (CT);
...
TAC: (TA) -> (AC); -
Составим граф из получившихся переходов, склеив одинаковые вершины
-
Найдем путь Эйлера и используя его, составим искомую строку GC -> CT -> TA -> AC -> CG -> GA -> AA -> AT -> TC -> CT
Для составления строки проведем операцию, обратную операции на шаге 3 для каждой пары последовательных вершин на пути.
GC -> CT: GCT
CT -> TA: CTA
TA -> AC: TAC
AC -> CG: ACG
CG -> GA: CGA
GA -> AA: GAA
AA -> AT: AAT
AT -> TC: ATC
TC -> CT: TCT
и наложим полученные фрагменты друг на друга в порядке, заданным путем:
GCT
CTA
TAC
ACG
CGA
GAA
AAT
ATC
TCT
GCTACGAATCT
Искомая строка: GCTACGAATCT
| Входные данные | Результат |
|---|---|
| K=2 AATCT ACGAA GCTAC |
GCTACGAATCT |
| K=3 AGCGDTA DTACCCC DTACTGG TGGADTA |
AGCGDTACTGGADTACCCC |