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

مسئله‎ استنتاج درخت تبارزایشی،  مسئله ای قدیمی در زیست شناسی است که در آن به دنبال درختی هستیم که شباهت موجودات را نشان دهد. الگوریتم های موجود برای بازسازی درخت تبارشناسی عموما الگوریتم هایی اکتشافی هستند. این الگوریتم ها مبتنی بر فهم و شهود ابداع کننده آن ها هستند و در مورد نحوه و میزان بهینه بودن آن ها هیچ تضمینی وجود ندارد. در مقابل، الگوریتم های تقریبی اگرچه جواب بهینه را پیدا نمی کنند (چون احتمالا این کار امکان پذیر نیست)، اما در مورد میزان فاصله جواب آن ها با جواب بهینه می توان محدوده ای مشخص کرد. در این مقاله، الگوریتمی تقریبی برای مسئله بازسازی درخت تبارشناسی تومور را بررسی می کنیم. این الگوریتم با تغییراتی در الگوریتمی برای مسئله درخت اشتاینر به دست می آید که پیش از این در ‎Alon‎, ‎N.‎, ‎Chor‎, ‎B.‎, ‎Pardi‎, ‎F.‎, ‎Rapoport‎, ‎A.‎, ‎‎IEEE/ACM Transactions on Computational Biology and‎ ‎Bioinformatics, ‎۷ (۲۰۰۸)‎, ‎۱۸۳-۱۸۷‎مطرح شده است. همچنین، یکی از کاربردهای علوم نظری کامپیوتر را در طراحی الگوریتم برای مسئله های بیوانفورماتیک بررسی خواهیم کرد.