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