Hamming

دستورالعمل‌ها

فاصله‌ی Hamming را بین دو رشته‌ی DNA حساب کنید.

بدن شما از سلول‌هایی تشکیل شده است که DNA دارند. این سلول‌ها به‌طور منظم فرسوده می‌شوند و باید جایگزین شوند؛ این کار را با تقسیم شدن به سلول‌های دختر انجام می‌دهند. در واقع، بدن انسان به‌طور میانگین در طول عمر خود حدود ۱۰ کوادریلیون تقسیم سلولی را تجربه می‌کند!

وقتی سلول‌ها تقسیم می‌شوند، DNA آن‌ها هم همانندسازی می‌کند. گاهی در جریان این فرایند اشتباهاتی رخ می‌دهد و پاره‌های تکی DNA با اطلاعات نادرست کدگذاری می‌شوند. اگر دو رشته‌ی DNA را با هم مقایسه کنیم و تفاوت‌هایشان را بشماریم، می‌توانیم ببینیم چند اشتباه رخ داده است. نام این پدیده، فاصله‌ی Hamming است.

DNA را با حروف C، A، G و T می‌خوانیم. دو رشته ممکن است این‌طور به نظر برسند:

GAGCCTACTAACGGGAT
CATCGTAATGACGGCCT
^ ^ ^  ^ ^    ^^

این دو ۷ تفاوت دارند و بنابراین فاصله‌ی Hamming برابر ۷ است.

فاصله‌ی Hamming در علم، نه فقط در زیست‌شناسی، برای کارهای زیادی به کار می‌آید؛ پس خوب است که با این اصطلاح آشنا باشید :)

فاصله‌ی Hamming فقط برای دنباله‌هایی با طول برابر تعریف شده است؛ بنابراین تلاش برای محاسبه‌ی آن بین دنباله‌هایی با طول متفاوت نباید کار کند. نحوه‌ی برخورد کلی با این وضعیت (مثلاً پرتاب یک استثنا در مقابل برگرداندن یک مقدار خاص) ممکن است بین زبان‌ها متفاوت باشد.

---

منبع

مسئله‌ی Calculating Point Mutations در Rosalind