الگوریتم‌های تقریبی برای بازسازی درخت تبارزایشی: کاربردهایی از علوم نظری کامپیوتر در زیست‌شناسی و بیوانفورماتیک

مسئله‎‏ٔ استنتاج درخت تبارزایشی،  مسئله‌ای قدیمی در زیست‌شناسی است که در آن به ‌دنبال درختی هستیم که شباهت موجودات را نشان دهد. الگوریتم‌های موجود برای بازسازی درخت تبارشناسی عموماً الگوریتم‌هایی اکتشافی هستند. این الگوریتم‌ها مبتنی‌بر فهم و شهود ابداع‌کنندهٔ آن‌ها هستند و در مورد نحوه و میزان بهینه ‌بودن آن‌ها هیچ تضمینی وجود ندارد. در مقابل، الگوریتم‌های تقریبی اگرچه جواب بهینه را پیدا نمی‌کنند (چون احتمالاً این کار امکان‌پذیر نیست)، اما در مورد میزان فاصلهٔ جواب آن‌ها با جواب بهینه می‌توان محدوده‌ای مشخص کرد. در این مقاله، الگوریتمی تقریبی برای مسئلهٔ بازسازی درخت تبارشناسی تومور را بررسی می‌کنیم. این الگوریتم با تغییراتی در الگوریتمی برای مسئلهٔ درخت اشتاینر به ‌دست می‌آید که پیش از این در مطرح شده است. همچنین، یکی از کاربردهای علوم نظری کامپیوتر را در طراحی الگوریتم برای مسئله‌های بیوانفورماتیک بررسی خواهیم کرد.