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

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