CRISPR-кассеты — восстановление последовательностей по наблюдаемым подпоследовательностям с применениями к бионформатике

<div>&nbsp;</div><div>Дипломная работа посвящена изучению CRISPR (Clustered Regularly&nbsp;</div><div>Interspaced Short Palindromic Repeats) кассет &mdash; специальных участков&nbsp;</div><div>генома, которые обеспечивают механизм противовирусной защиты клетки и&nbsp;</div><div>имеют особую, ярко выраженную, структуру. Представленное исследование&nbsp;</div><div>выполнено в рамках совместного проекта с Липняговым А. И. на базе УНЦБ&nbsp;</div><div>ИППИ РАН и детально описывает анализ существующей информации о&nbsp;</div><div>системах CRISPR с использованием математических методов и подходов. В&nbsp;</div><div>частности, в работе подробно рассмотрен основополагающий этап проекта,&nbsp;</div><div>заключающийся в нахождении некоторого общего объекта для каждой&nbsp;</div><div>группы кассет со сходной структурой (кластеров кассет). Построение такого&nbsp;</div><div>объекта представляет из себя NP-полную проблему, и для ее решения с&nbsp;</div><div>использованием реальных данных в работе были представлены&nbsp;</div><div>эвристические подходы, в частности алгоритм покрытия графа накрытий&nbsp;</div><div>циклами, который находит приближенное частное решение. В рамках&nbsp;</div><div>проекта особый интерес представляла задача точного поиска всех таких&nbsp;</div><div>объектов; данная работа детально рассматривает ее решение на основе&nbsp;</div><div>нескольких ключевых алгоритмов на строковых графах.</div>