Сравнение геномов (редакционное расстояние) dnao10

Первая олимпиада Олмат.Программирование. 23.02.26

Тема: Биотехнологии Уровень: Профи

📜 Пятая находка

В подземном архиве старой биолаборатории обнаружены два фрагмента ДНК, сохранённые в текстовом формате.

Эти последовательности состоят только из нуклеотидов:

A — аденин C — цитозин G — гуанин T — тимин

Учёные прошлого пытались определить, насколько сильно один образец мутировал относительно другого. Твоя задача — восстановить степень различия между этими двумя генетическими фрагментами.

🧠 Немного о технологии

В молекулярной биологии сравнение последовательностей ДНК является ключевым инструментом анализа.

Геном любого организма — это длинная цепочка нуклеотидов A, C, G и T. При репликации, воздействии среды или эволюционных процессах в этой цепочке могут происходить изменения:

• появляются лишние нуклеотиды,
• исчезают участки цепи,
• один нуклеотид заменяется другим.

Даже одно такое изменение может повлиять на синтез белков и работу клеток.

Для количественной оценки различий между последовательностями используется формальный показатель расстояния между ними.

📌 Редакционное расстояние

Редакционное расстояние моделирует реальные мутационные процессы:

• вставка нуклеотида (инсерция),
• удаление нуклеотида (делеция),
• замена одного нуклеотида другим (точечная мутация).

Минимальное количество таких изменений показывает, насколько один генетический фрагмент отличается от другого.

Этот подход применяется при:

• сравнении штаммов вирусов,
• поиске мутаций в генах,
• анализе эволюционного родства организмов.

⚙️ А где используется?

В реальной биоинформатике подобные вычисления используются для:

• сравнения ДНК пациента с эталонным геномом человека;
• отслеживания мутаций вирусов при эпидемиологическом мониторинге;
• анализа древней ДНК;
• построения филогенетических деревьев.

Полученное число отражает минимальное количество мутационных событий, разделяющих два образца.

📌 Задача

Даны две строки, каждая из которых представляет фрагмент ДНК.

Необходимо определить минимальное количество мутаций (вставка, удаление, замена нуклеотида), чтобы преобразовать первую последовательность во вторую.

📥 Формат входных данных

Вводятся две строки:

• первая строка s — фрагмент ДНК
• вторая строка t — фрагмент ДНК

Ограничения

• 1 ≤ |s|, |t| ≤ 2000
• строки состоят только из символов A, C, G, T

📤 Формат выходных данных

Выведите одно целое число — минимальное количество мутационных изменений между двумя фрагментами ДНК.

📘 Примеры

Пример 1

Входные данные: ACGT ACGG

Выходные данные: 1

Пример 2

Входные данные: GATTACA GACTATA

Выходные данные: 2

Пример 3

Входные данные: AAAA TTTT

Выходные данные: 4