Восстановление последовательности по ее подпоследовательностям с применением к задаче сборки геномов

<p>ВКР посвящена решению различных вариантов задачи восстановления последовательности по ее подпоследовательностям.</p><p>Приведены некоторые существующие теоретические формулировки задачи восстановления и полученные ранее результаты.</p><p>Описаны некоторые известные эффективные алгоритмы для решения частных случаев задачи восстановления&nbsp; и известные приближенные алгоритмы, для некоторых задач, точное решение которых не найдено, но которые полезны для практических задач.</p><p>В работе реализован известный алгоритм Левенштейна для восстановления слов по подпоследовательностям, предполагающий некоторые ограничения на множество исходных фрагментов, и оценена его сложность. Делается вывод, что данный алгоритм вряд ли применим на практике, так как он корректно решает задачу однозначного восстановления только при соблюдении определенных ограничений, которые могут не выполнятся на практике. Отметим, что, однако, этот алгоритм является одним из самых эффективных алгоритмов решения этой задачи.</p><p>Рассмотрено одно из популярных практических применений данной задачи на примере сборки генома. Обсуждаются возникающие при этом сложности, так как исходные данные не удовлетворяют ограничениям, присущим наиболее известным алгоритмам решения задачи.</p><p>В ВКР предложен приближенный алгоритм решения задачи восстановления слова по всем его подсловам с возможными стираниями на месте которых ставится дополнительный символ. Оценена сложность алгоритма и предложена его программная реализация. Для анализа того, насколько эффективно он решает задачу восстановления, проведены многочисленные тесты программы на различных входных данных. Показано, что в среднем предложенный алгоритм правильно решает задачу (восстанавливает именно то слово, из которого были прочитаны фрагменты) для множества всех фрагментов длины больше чем n/2, где n &ndash; длина исходного слова. При этом количество стираний во фрагменте должно быть не больше двадцати процентов от числа символов в нем.</p>