Hamming

Вказівки

Обчисліть відстань Геммінга між двома ланцюгами ДНК.

Наше тіло складається з клітин, які містять ДНК. Ці клітини регулярно зношуються та потребують заміни, а замінюються вони, ділячись на дочірні клітини. Насправді, середнє людське тіло за все життя переживає близько 10 квадрильйонів поділів клітин!

Коли клітини діляться, їхня ДНК теж реплікується. Іноді під час цього процесу трапляються помилки, і окремі фрагменти ДНК закодовуються неправильною інформацією. Якщо порівняти два ланцюги ДНК та порахувати відмінності між ними, можна побачити, скільки помилок сталося. Це називають «відстанню Геммінга».

Ми читаємо ДНК за допомогою літер C, A, G та T. Два ланцюги можуть мати такий вигляд:

GAGCCTACTAACGGGAT
CATCGTAATGACGGCCT
^ ^ ^  ^ ^    ^^

Між ними 7 відмінностей, а отже, відстань Геммінга дорівнює 7.

Відстань Геммінга корисна для багатьох речей у науці, не лише в біології, тож із цим поняттям варто бути знайомими :)

Нотатки щодо реалізації

Відстань Геммінга визначена лише для послідовностей однакової довжини, тож спроба обчислити її для послідовностей різної довжини не повинна спрацювати.

---

Джерело

Задача Calculating Point Mutations на Rosalind