بررسی روش شاخص گذاری فاصله در گراف های توالی

تمام حیات موجودات زنده از جمله انسان، از ماده ژنتیکی آن ها یعنی دیانای سرچشمه میگیرد. به همین علت یافتن ساختار این ماده و تعیین ترتیب توالیهای موجود در آن که اصطلاحا ژنوم نامیده میشود، حائز اهمیت است. با گذشت زمان، ژنوم موجودات زنده دچار جهش شده و این جهش ها باعث ایجاد تنوع ژنتیکی و در نهایت تنوع ظاهری میشوند. با کاهش هزینه توالی یابی دیانای و ظهور فناوریهای جدید توالی یابی کل ژنوم، توالی های ژنوم بیشتری تولید میشود و ژنومهای مرجع به عنوان راهنما برای ساخت ژنومهای جدید مورد استفاده قرار میگیرند و این امکان را فراهم میسازند که سریعتر ژنوم کامل مونتاژ شود. استفاده از ژنوم خطی که شامل ژنوم یک موجود از یک گونه میباشد و از هر ژن تنها یک حالت را در خود جای می دهد به عنوان یک ژنوم مرجع ضعیف عمل میکند زیرا تنوع ژنتیکی موجود در یک جمعیت یا یک گونه را نادیده میگیرد و زمانی که نمونه ژنومهای جدید بر اساس مرجع خطی توالییابی شوند دچار جهتگیری به سمت مرجع میشوند. برای جلوگیری از این جهتگیری، لازم است ژنومی را به عنوان مرجع در نظر گرفت که تنوع ژنتیکی را در خود جای داده باشد و ساختار داده ای که با آن میتوان این نیاز را برآورده کرد گراف است. گراف های ژنوم نسبت به ژنومهای خطی پیچیدگی بیشتری دارند و توابعی که محاسبه آنها در ژنوم خطی بسیار ساده است در زمینه گرافها پیچیده میباشند. یکی از این توابع محاسبه فاصله است که در زمینه های مختلف تجزیه و تحلیل ژنوم از آن استفاده میشود. در این مقاله به بررسی الگوریتمی میپردازیم که با استفاده از شاخصگذاری فاصله، کوتاه ترین فاصله بین دو موقعیت در گرافتوالی را محاسبه می کند. همچنین از نظر زمان اجرا، به مقایسه این الگوریتم با الگوریتم دایجسترا و روشهای مبتنی بر مسیر میپردازیم.

Keywords:

گراف ژنوم , گراف توالی , گراف تنوع , کوتاه ترین فاصله , شاخص گذاری فاصله.