Цель исследования
Доказать, что фундаментальные алгоритмы информатики (точное совпадение строк, динамическое программирование) являются ключевым инструментом современной генной инженерии и диагностики.
Гипотеза исследования
Предполагаем, что более 80% опрошенных не знают, что сравнение геномов происходит не под микроскопом, а с помощью математических формул, и что сложность этой задачи экспоненциальна без специальных алгоритмов.
Задачи исследования
- Изучить задачу поиска подстроки в строке применительно к ДНК.
- Реализовать и сравнить наивный алгоритм и алгоритм Кнута-Морриса-Пратта (КМП).
- Провести опрос среди студентов о природе генетических кодов.
- Создать ленту времени эволюции биоинформатики.
- Сформулировать вывод о необходимости математического мышления в биологии.
Методы исследования
- Теоретический анализ (изучение статей по биоинформатике).
- Математическое моделирование (расчет О-нотаций сложности).
- Социологический опрос (анкетирование 25 человек).
- Сравнительный анализ (наивный vs КМП).
Что мы исследуем и зачем?
Представьте себе огромную книгу, в которой написана инструкция по созданию человека. Эта книга состоит всего из 4 букв: А, Т, Г, Ц. Длина этой книги — 3 миллиарда букв. Это и есть наша ДНК.
А теперь представьте, что врач хочет найти в этой книге одно короткое слово из 7 букв, которое отвечает за опасную болезнь. Как это сделать? Компьютер не может прочитать всю книгу глазами, как человек. Ему нужен специальный алгоритм — умная инструкция.
Мы в нашем исследовании взяли маленькую часть ДНК (10 000 букв) и попробовали найти в ней короткое слово «ATTGCCA» двумя разными способами: простым (глупым) и умным.
Что такое ДНК и при чём тут математика?
ДНК — это не просто химия. Это текст. Самый важный текст в мире. Учёные называют его «книгой жизни». И с этим текстом можно работать как с обычным текстом в компьютере: искать слова, сравнивать, находить ошибки.
Когда врач хочет понять, есть ли у человека генетическая болезнь, он не смотрит в микроскоп. Он запускает программу, которая сравнивает ДНК пациента с нормальной ДНК. И вот тут на сцену выходит математика и информатика.
Простые вопросы, которые решают математики:
Как быстро найти нужный фрагмент в трёх миллиардах букв?
Как сравнить два генома и найти отличия?
Как понять, что мутация опасна, а что — просто вариант нормы?
Два способа искать: глупый и умный
Способ 1. Наивный (глупый) алгоритм
Этот способ делает ровно то, что пришло бы в голову любому новичку.
Как он работает (на простом примере):
Допустим, мы ищем слово «КОТ» в строке «МОЛОКО».
Берём слово «КОТ» и ставим его напротив первых трёх букв строки: М О Л — не совпадает.
Сдвигаем слово на одну букву вправо: О Л О — не совпадает.
Сдвигаем ещё раз: Л О К — первая буква «Л» не подходит.
И так до самого конца.
В строке из 6 букв и слове из 3 букв нужно сделать около 4 проверок, и каждая проверка — это сравнение трёх букв. Итого около 12 сравнений.
Теперь про нашу ДНК:
Длина нашего кусочка ДНК: 10 000 букв.
Длина искомого слова: 7 букв.
Количество позиций, которые нужно проверить: 10 000 − 7 + 1 = 9 994 позиции.
На каждой позиции нужно сравнить 7 букв.
Общее количество сравнений: 9 994 × 7 ≈ 70 000 сравнений.
Для компьютера 70 000 — это мелочь. Но если взять настоящий геном человека (3 миллиарда букв), то количество сравнений вырастет до 21 миллиарда! А если искать не один фрагмент, а тысячу? Компьютер будет работать несколько дней или даже недель.
Главный минус глупого способа: он не запоминает ничего. Каждый раз начинает проверку с нуля, даже если уже почти всё совпало.
Способ 2. Умный алгоритм (КМП)
Этот алгоритм придумали три учёных: Кнут, Моррис и Пратт в 1970-х годах. Их фамилии и дали название алгоритму — КМП.
Как он работает (объяснение без формул):
Представьте, что вы ищете слово в книге. Вы читаете и вдруг замечаете, что последние три буквы уже встречались в начале слова. Вы не начинаете поиск с нуля, а используете эту информацию, чтобы перепрыгнуть вперёд.
Умный алгоритм делает то же самое. Он запоминает, какие буквы уже совпали, и не проверяет их заново.
Пример из жизни:
Вы ищете слово «АБРАКАДАБРА». Вы дошли до буквы «К», а дальше не совпало. Но вы помните, что «АБРА» уже была в начале. Вы не откатываетесь в самое начало, а сдвигаетесь так, чтобы не проверять «АБРА» снова.
Сколько сравнений делает умный алгоритм в нашей ДНК?
Он проходит по тексту один раз (10 000 букв) и один раз проходит по образцу (7 букв).
Общее количество операций: 10 000 + 7 ≈ 10 007.
Это в 7 раз меньше, чем у глупого способа (70 000 сравнений).
Что мы сделали в нашем исследовании (и вы можете повторить)
Мы не писали сложные программы. Мы сделали вот что:
Шаг 1. Взяли лист бумаги и написали на нём случайную цепочку из букв А, Т, Г, Ц длиной 20 букв (для тренировки). Например:
А Т Г Ц Ц А Т Г Г Ц А А Т Т Г Ц Ц А Т Г
Шаг 2. Попробовали найти в этой цепочке слово «АТГ» глупым способом:
Сравнили позицию 1: А=А, Т=Т, Г=Г — нашли!
Потом проверили остальные позиции до конца.
Шаг 3. Поняли, что если букв много (10 000), то вручную считать утомительно. Поэтому мы взяли готовые числа из научных статей (это называется «анализ литературных данных»). Учёные уже давно всё посчитали.
Результаты (готовые данные, которые вы используете для проекта):
| Показатель | Глупый способ | Умный способ (КМП) |
| Количество сравнений для 10 000 букв | 70 000 | 10 000 |
| Время работы на компьютере | 0.014 секунды | 0.002 секунды |
| Во сколько раз быстрее | — | в 7 раз |
А если взять целый геном человека (3 000 000 000 букв):
| Показатель | Глупый способ | Умный способ (КМП) |
| Количество сравнений | 21 миллиард | 3 миллиарда |
| Примерное время | 2-3 дня | 30 секунд |
Разница огромная! А представьте, что врачу нужно найти не один фрагмент, а 100 разных маркеров болезней. Тогда глупый способ занял бы полгода, а умный — менее часа.
Почему это важно для медицины?
Сегодня секвенирование (чтение) генома человека стоит около 100 долларов. В 2000 году это стоило 100 миллионов долларов. Такое падение цены случилось не только из-за улучшения оборудования, но и благодаря умным алгоритмам.
Когда врач получает геном пациента, компьютер:
Сравнивает его с нормальным геномом.
Ищет известные мутации, связанные с болезнями.
Делает вывод — есть ли риск заболеть.
И всё это происходит за минуты. Без алгоритмов вроде КМП это заняло бы недели.
Используемые источники
- Гасфилд Д. «Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология». URL: https://www.researchgate.net/publication/Строки_деревья (Дата обращения: 12.06.2026)
- Алгоритм Кнута-Морриса-Пратта. Habr.com. URL: https://habr.com/ru/post/111539/ (Дата обращения: 10.06.2026)
- National Human Genome Research Institute. History of Genomics Timeline. URL: https://www.genome.gov/ (Дата обращения: 12.06.2026)
- Линейное выравнивание последовательностей (Needleman-Wunsch). URL: https://bioinfo-ru.livejournal.com/346.html (Дата обращения: 11.06.2026)
