|
بازیابی موقعیت توالی مورد نظر q در دو مرحله اجرا می شود: جستجوی HT و جستجوی دودویی SA. اگر پیشوند Q طول q (q-gram) زیر رشته ای از توالی است، ما محدوده ای را پیدا می کنیم که در آن q-gram به SA تعلق دارد (با استفاده از معادله ی ۱) . به عبارت دیگر محدودی R یک محدوده ی خالی را بر می گرداند که نشان می دهد که Q در توالی قرار ندارد. اگر محدوده ی بازگردانی شده خالی نباشد، ما موقعیت هایی را پیدا می-کنیم که Q در آنها با جستجوی دودویی زیر رشته ی Q ] |Q| − ۱ [ در توالی اتفاق می افتد. به صورت نظری، جستجوی زیر رشته ی طول m در یک رشته از طول N با استفاده از SA می تواند در زمان O (mlogN) در بد بینانه ترین حالت به کار گرفته شود. شاخص جدول درهم سازی می تواند طول رشته ی مورد جستجو مانند (m′ = m − q) و اندازه ی محدوده ی جستجو مانند (n′ ≪ N) را کاهش دهد. زمانیکه توالی مرجع ساختمان GRCH37 ژنوم انسان است و q برابر ۱۴ است، طول توالی بسته بندی شده ۲، ۸۶۱، ۳۴۳، ۷۶۶ و میانگین اندازه ی محدوده ی جستجو ۱۴٫۱۲ است. ازمایش ما نشان داد که شاخص جدول درهم سازی زمان جستجو را به میزان چشمگیری کاهش می دهد (بنگرید به فایل پیوست ۱).
نقشه برداری هیبرید: یافتن نواحی همترازی کاندید (CAR)
نقشه برداری هیبرید از روش seed-and-extend مشابهی با سایر ابزارهای مبتنی بر HT پیروی می کند. یک MR(ناحیه ی تطابق) زیر رشته ی مشترک بین توالی مرجع و رید است. ‘sp’ را به عنوان ناحیه ی شروع توالی مرجع در نظر بگیرید که MR در آن کار دارد.
ما هر MR را به صورت <dv, ro, L> مشخص می کنیم که در آن ‘ro’ ( افست رید) ناحیه ی شروع در رید است که MR در آنجا قرار می گیرد، ‘dv’ ( مقادیر دیاگونال ) به صورت dv = sp – ro تعریف می شود و ‘L’ طول MR است. با توجه به یک MR طول – m′ ، (m′ − q + 1) تعداد q-gram وجود دارد که مقادیر دیاگونال یکسان و افست های متوالی دارند. مقادیر دیاگونال برابر هستند که نشان می دهد که MRهای متناظر در توالی مرجع نزدیک یکدیگر قرار دارند. CAR (ناحیه ی همترازی کاندید) لیستی از MRهاست که نزدیک یکدیگر قرار دارند و بوسیله ی ‘ro’ مرتب شده اند. ما یک CAR را به صورت یک seed تعریف می کنیم و تنها مناطق ناجور در CAR را همتراز می کنیم.
روش یافتن MRها و CARها به صورت زیر است: ۱) بازیابی محدوده ی SA هر q-gram با استفاده از HT و SA؛ ۲) محاسبه ی مقادیر دیاگونال ۳) دسته بندی با مقدار دیاگونال و افست.؛ ۴) گروه بندی MRها با مقادیر دیاگونال یکسان و افست های پشت سرهم ۵) ترکیب کردن MRهای مجاور به درون CARها ۶) دست بندی CARها با بازهای جور از بالا به پایین. برای مثال باتوجه به رید (r = GCCATG) و طول q-gram (q = 2) و شاخص هیبرید ساخته شده در شکل ۱، ما می توانیم MRها و CARها را به صورت زیر پیدا کنیم:
I. بازیابی محدوده ی SA هر q-gram با استفاده از HT و SA
موقعیت صفرم q-gram : (GC: SA[10, 11])
موقعیت اول q-gram: (CC: SA[8])
موقعیت دوم q-gram: (CA: SA[6, 7])
موقعیت سوم q-gram: (AT: SA[3, 4])
موقعیت چهارم q-gram: (TG: SA[15])
II. محاسبه ی مقادیر دیاگونال
(GC, 5, 0)، (GC, 11, 0) ، (CC, 11, 1) ، (CA, 4, 2) ، (CA, 11,2) ، (AT, −۲, ۳)، (AT, 4, 3)، (TG, 4, 4)
III. دسته بندی با مقدار دیاگونال و افست.؛
(AT, −۲, ۳)، (CA, 4, 2) ، (AT, 4, 3)، (TG, 4, 4)، (GC, 5, 0) ، (GC, 11, 0) ، (CC, 11, 1) ، (CA, 11, 2)
IV. گروه بندی MRها با مقادیر دیاگونال یکسان و افست های پشت سرهم
MR0: (AT, −۲, ۳, ۲) ← (AT, −۲, ۳)
MR1: (CATG, 4, 2, 4) ← (CA, 4, 2), (AT, 4, 3), (TG, 4, 4)
MR2: (GC, 5, 0, 2) ← (GC, 5, 0)
MR3: (GCCA, 11, 0, 4) ← (GC, 11, 0), (CC, 11, 1), (CA,
۱۱, ۲)
V. ترکیب کردن MRهای مجاور به درون CARها و تنظیم بازهای جور
CAR0: (MR0; 2)
CAR1: (MR1, MR2; 5)
CAR2: (MR3; 4)
VI. دسته بندی CARها با بازهای جور
CAR1: (MR1, MR2; 5)
CAR0: (MR3; 2)
CAR2: (MR2; 2)
اگرچه مقادیر دیاگونال دو MR مجاور متفاوت است، اما این دو می توانند در یک CAR جای بگیرند به شرطی که بازهای اضافه شده یا حذف شده ای بین آنها وجود داشته باشد. در مورد CAR1، اختلاف مقدار بین مقدار دیاگونال MR1 و مقدار دیاگونال MR2 برابر ۱ است و یک باز وارد شده (C) بین MR1 و MR2 وجود دارد. ما این مقدار را به مجاورت نسبت می دهیم و از این مقدار به منظور تنظیم مقدار کجاز اندازه ی حذف و اضافه بین MRها استفاده می کنیم.
به منظور یافتن کارامدتر MRها و CARها، ما از سه فراین کاوشی استفاده می کنیم. طول رید و میزان خطا را به ترتیب m و ε در نظر بگیرید. اولین روش کاوشی این است که یک زیر رشته با طول حداقل m/(k + 1) بین دو رید طول m با اختلاف k وجود دارد. فرض کنید λ = εm تعداد خطاهای مورد انتظار در یک رید باشد و x را یک متغییر تصادفی در نظر بگیرید. ما می توانیم شانس مشاهده ی یک رید با خطاهای k را به صورت زیر محاسبه کنیم :
فرمول ۲ معادله توزیع تجمعی x است. بر اساس معادله ی ۲ ما قادر هستیم مقدار ریدها با خطای k را محاسبه کنیم. اگر ما k = 1.5λ تنظیم کنیم، مقدار ریدها با خطاهای ۱٫۵λ به ۰٫۹ میل می کند و ما می توانیم از q-gram با طول m/(1.5λ + ۱) استفاده کنیم. استفاده از یک q-gram با طول یکسان به عنوان زیر رشته ی مشترک تعداد MRها و CARها را کاهش می دهد.
ثانیا، از آنجایی که q-gram که در مناطق زیادی از توالی وجود دارد تفکیک کننده ی خوبی نیست، چنین q-gram نسبت به q-gram که در مناطق کمتر وجود دارد وزن کمتری می گیرد. این روش مبتنی بر عکس فراوانی سند (IDF) است که معمولا در زمینه بازیابی اطلاعات استفاده می شود. IDF یک شیوه ی وزن دهی است که مشخص می کند که آیا یک کلمه در کل سند مشترک است یا نه. با استفاده از این روش، می توانیم q-gram های با وزن پایین را فیلتر کنیم و در نتیجه از MRها و و CARهای نامطلوب خلاص شویم.
نهایتا، با توجه به رید (r) و رشته های S1 و S2 ، هر دو طول m ، اگر تعداد بازهای جور بین r و S1 بیشتر از تعداد بازهای جور بین r و S2 باشد مقدار اختلاف بین r و S1 کوچکتر از تعداد اختلاف بین r و S2 خواهد بود. این روش را می توان برای دسته بندی CARها با استفاده از تعداد بازهای جور و فیلتر کردن CARهای با رتبه ی پایین استفاده کرد.
نقشه برداری هیبرید : همترازی ناحیه ی همترازی کاندید (CAR).
برای همترازی CARهای با رتبه ی بالا، ما نواحی ناجور در هر CAR را همتراز می کنیم، زیرا MRها کاملا همتراز شده اند (جور). ما نواحی ناجور را به سه دسته تقسیم می کنیم: سمت چپ ترین ناحیه ی ناجور (LMUR) که ناحیه ی ناجور سمت چپ اولین MR در CAR است، سمت راست ترین ناحیه ی ناجور (RMUR) که ناحیه ی ناجور راست اخرین MR در CAR است و نواحی ناجور بین دو MR (MRURs) . نواحی جور و ناجور به دلیل وجود جفت شدگی های اشتباهی، دخول و حذف می توانند از هم جدا شوند. ما این علل جدایی را در شکل ۲ بررسی می کنیم. در مورد LMUR و RMUR، اگر تنها بازهای مجاور بین این ناحیه ی ناجور و MR جفت شدگی اشتباهی باشند و بازهای دیگر جور باشند، علت جدایی آن عبارت است از جفت شدگی اشتباهی؛ اگر این بازها نتیجه ی دخول باشند پس عامل جدایی دخول است، و اگر این بازها حذف شده باشند و بقیه جور باشند عامل جدایی حذف است در غیر اینصورت عامل جدایی مرکب است. اطلاعات جفت شدگی اشتباه، دخول و حذف به وضوح نشان می دهد که این نواحی چطور همتراز می شوند. بنابراین، ما می توانیم از الگوریتم نیدلمن- وونش تنها برای نواحی ناجوری که نتیجه ی چند عامل هستند استفاده کنیم بدین ترتیب می-توانیم زمان محاسبات روش برنامه نوبسی پویای الگوریتم نیدلمن- وونش را کاهش دهیم.
عوامل زیادی برای جداییMRUR وجود دارد که در شکل ۲ اشاره شده است. این عوامل را می توان به صورت جفت شدگی ناجور، دخول، حذف و ترکیبی از اینها دسته بندی کرد. در رابطه با دخول، اگر چندین باز (α) بین دو MR مجاور در یک رید وجود داشته باشد، ولی بازی در توالی وجود نداشته باشد، پس می توان باز α را وارد کرد (دخول ۱). اگر بازهای α بین دو MR مجاور در یک رید وجود داشته باشند و بازهای β در تولی همپوشانی شوند، می تواند بازهای α + β را وارد کرد (دخول ۲). اگر بازهای α در یک رید و بازهای β در توالی همپوشانی داشته باشند و α کوچکتر از β باشد می توان بازهای β – α را وارد کرد (دخول ۳). در رابطه با حذف، اگر چندین باز β بین دو MR مجاور در یک توالی وجود داشته باشد، ولی بازی در رید وجود نداشته باشد، پس می توان باز β راحذف کرد (حذف ۱). اگر بازهای β بین دو MR مجاور در یک توالی وجود داشته باشند و بازهای αدر تولی همپوشانی شوند، می تواند بازهای α + β را حذف کرد (حذف ۲). اگر بازهای β در یک توالی و بازهای α در یک رید همپوشانی داشته باشند و α بزرگتر از β باشد می توان بازهای α − β را حذف کرد (حذف ۳). در رابطه با جفت شدگی اشتباهی، اگر یک باز بین دو MR مجاور در یک رید وجود داشته باشد و یک باز در توالی موجود باشد این بازهای می توانند اشتباهی جفت شوند (جفت شدگی اشتباهی). به جز تمام عواملی که در بالا به آنها اشاره شد یکی دیگر از این عوامل ترکیب چندعامل است. ما همچنین الگوریتم نیدلمن- وونش را تنها برای MRUR چندعاملی به کار ببریم تا بار برنامه نویسی پویای این الگوریتم را کاهش دهیم. برای مثال در مورد CAR1 که در شکل ۳ نشان داده شده است، در اینجا تنها یک MRUR بین MR1 و MR2 وجود دارد. از طریق دخول ۲ ما یک دخول بین MR1 و MR2 اعمال می کنیم و ۲M1I3M ((CIGAR format) را بدست می آوریم. در مورد CAR2، یک RMUR وجود دارد و عامل ترکیبی است. بنابراین ما می توانیم نیدلمن-وونش را بر RMUR اعمال کنیم و ۴M1I1M یا ۵M1I (CIGAR format) را بدست اوریم.
|
