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

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