نظریه توالی‌یابی دی‌ان‌ای

توالی‌یابی، یک مساله پوشش

همه‌ی روش‌های اصلی توالی‌یابی دی‌ان‌ای، بر پایه‌ی خواندن تکه‌های دی‌ان‌ای و بازسازی دی‌ان‌ای از روی این تکه‌ها، یا به وسیله بازسازی توالی و یا هم‌ترازسازی توالی است. مساله پوشش، یک مساله انتزاعی برای هردوی آن‌هاست.

بیش از یک قرن، ریاضیدانان ویژگی‌های انتزاعی پوشش را مطالعه قرار دادند. با این حال، کاربردهای مستقیم نتایج آن‌ها به طور کلی امکان‌پذیر نبوده. به این معنا که الگوریتم‌های بدست‌آمده از آن‌ها زمان زیادی برای اجرا نیاز دارند. یکی از مثال‌های این الگوریتم‌ها، پیکربندی استیون است.

کاربردهای اولیه‌ی نظریه توالی‌یابی به کمک نظریه احتمال

فرض کنید فرایند بالا را به این شکل مدل کنیم که ${\displaystyle L}$

${\displaystyle E[C]=Pr[C=1]=1-{\left[1-\frac{L}{G}\right]}^N}$

و اگر فرض کنیم ${\displaystyle N\gg 1}$

${\displaystyle {\left[1-\frac{L}{G}\right]}^N\sim e^{-\frac{NL}{G}}⟹E[C]=1-e^{-\frac{NL}{G}}}$

که ${\displaystyle R=\frac{NL}{G}}$

نظریه لندر-واترمن

در سال ۱۹۸۸، اریک لندر و مایکل واترمن یک مقاله مهم در این زمینه منتشر کردند. تمرکز آن‌ها روی مسأله نگاشت ژن بود که در حالت انتزاعی خیلی به مسأله توالی‌یابی نزدیک است. مدل آن‌ها در پروژه ژنوم انسان نیز استفاده شد و همچنان نقش اساسی‌ای در توالی‌یابی دی‌ان‌ای دارد. یکی از پراستفاده‌ترین نتایج مدل آن‌ها بدست آوردن امیدریاضی تعداد وربستهاست.

${\displaystyle E[contigs]=N{e}^{-R}}$

ترفند توقفگاه

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

• زیست‌شناسی محاسباتی
• زیست‌داده‌ورزی
• زیست‌شناسی ریاضیاتی و نظری
• امتیاز سولستون