اتصال-همسایگی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

اتصال-همسایگی (به انگلیسی: neighbor-joining) در بیوانفورماتیک یک روش خوشه بندی پایین به بالا برای ساخت (فنوگرام) است؛ این روش توسط Naruya Saitou و Masatoshi Nei ارائه شده است. این روش معمولا برای درختهایی که بر پایه داده های توالی دی انی ای و پروتئین هستند به کار میرود. این الگوریتم به اطلاعاتی در مورد فاصله بین یک جفت تاگزا(taxa)(گونه ها یا توالی ها ) در درخت نیاز دارد.

این درخت با روش اتصال-همسایگی بر اساس 23 نوع از اطلاعات ژنتیکی در سال 2002 ساخته شده است و تخمینی از فاصله ژنتیکی 18 گروه انسان موجود روی زمین است .[۱]

توضیح الگوریتم[ویرایش]

الگوریتم ابتدا از یک درخت با توپولوژی ستاره مانند شروع میشود و پنج مرحله ی زیر را تکرار میکند تا زمانی که توپولوژی نهایی درخت همراه با طول شاخه ها مشخص شوند.

  1. بر اساس ماتریس فاصله ها ماتریس Q را که در زیر تعریف میشود محاسبه کنید.
  2. جفت تاگزا ای در Q که کمترین مقدار را دارند پیدا کنید. یک گره اضافه کنید که این دو تاگزا را به هم وصل کند.
  3. فاصله ی تاگزاهای موجود در این جفت تا گره جدید را محاسبه کنید.
  4. فاصله ی تاگزاهای دیگر تا گره جدید را محاسبه کنید.
  5. جفت تاگزای متصل شده به هم را یک تاکسون در نظر بگیرید و با توجه به فواصل جدید به دست آمده مجددا از مرحله ی یک الگوریتم را تکرار کنید.

ماتریس Q[ویرایش]

بر اساس ماتریس فاصله ی بین r تا تاگزا، ماتریس Q را به شکل زیر حساب کنید:

Q(i,j)=(r-2)d(i,j)-\sum_{k=1}^r d(i,k) - \sum_{k=1}^r d(j,k)

d(i,j) فاصله ی بین تاکسون i و j است.

فاصله ی بین اعضای جفت شده در کد جدید[ویرایش]

اگر f و g دو تاکسونی باشند که اخیرا با هم جفت شده اند و u گره ی جدید باشد، فاصله ی f تا u و فاصله ی g تا u به صورت زیر محاسبه میشوند:

d(f,u)=\frac{1}{2}d(f,g)+\frac{1}{2(r-2)} \left [ \sum_{k=1}^r d(f,k) - \sum_{k=1}^r d(g,k) \right ] \quad

و طبق خاصیت انعکاسی:

d(g,u)=d(f,g)-d(f,u) \quad

فاصله ی بین بقیه تاگزاها(taxa)در کد جدید[ویرایش]

فاصله ی بقیه ی تاکسون ها تا u توسط فرمول زیر محاسبه میشود:

d(u,k)=\frac{1}{2} [d(g,k)+d(f,k)-d(f,g)]

پیچیدگی[ویرایش]

اجرای این الگوریتم روی r تاگزا نیاز به r-3 تکرار دارد و در هر تکرار یک ماتریس r\times r ساخته میشود و مورد جستجو قرار میگیرد. در نتیجه پیچیدگی الگوریتم برابر است با O(r^3).

مثال[ویرایش]

فرض کنید چهار تاکسون با نامهای A,B،C,D با ماتریس فاصله ی زیر داریم:

D C B A
A 14 11 7 0
B 9 6 0 7
C 7 0 6 11
D 0 7 9 14

مقادیر زیر برای ماتریس Q به دست می آیند:

D C B A
A 34− 34− 40− 0
B 34− 34− 0 40−
C 40− 0 34− 34−
D 0 40− 34− 34−

در مثال بالا دو تاگزا کمترین مقدار یعنی 40- را دارند. هرکدام از آنها میتوانند برای مرحله ی بعد انتخاب شوند.ما در این مثال فرض میکنیم A,B متصل شده باشند. اگر گره ی جدید را با u نشان دهیم طول شاخه های {A, u} و {B, u} به ترتیب 6 و 1 خواهد بود.

با استفاده از فرمول توضیح داده شده در بالا d(u,k)ها را حساب کرده و ماتریس فاصله ها را به روز میکنیم.

D C AB
AB 8 5 0
C 7 0 5
D 0 7 8

در این مثال اگر یکبار دیگر مراحل فوق را روی این ماتریس تکرار کنیم، جواب نهایی حاصل میشود.

فواید و مضرات[ویرایش]

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

بزرگترین مزیت روش اتصال-همسایگی بر دیگر روشها کارآمد بودن این روش از نظر محاسباتی است زیرا یک الگوریتم چندجمله ای است. در نتیجه در مواردی که روشهای دیگر (مانند: e.g. minimum evolution, maximum parsimony, maximum likelihood) بسیار زمانبر هستند میتوان از این روش استفاده کرد. برخلاف الگوریتم روش جفت گروه بدون وزن با میانگین حسابی در این روش فرض ساعت مولکولی را نداریم یعنی فرض نمیکنیم که اجداد با یک نسبت تکامل می یابند، بعلاوه درخت حاصل از این روش یک درخت بدون ریشه است؛ هرچند میتوان با استفاده از outgroup این درخت را ریشه دار کرد.

آتسون[۲] ثابت کرده است که اگر اختلاف هر عنصر در ماتریس فاصله ها با فاصله واقعی کمتر از نصف طول کوچکترین شاخه در درخت باشد آنگاه این روش درخت درست را می سازد.

RapidNJ و NINJA دو پیاده سازی سریع از این روش اند.

منابع[ویرایش]

  1. Saitou. Kyushu Museum. 2002. February 2, 2007
  2. Atteson K (1997). "The performance of neighbor-joining algorithms of phylogeny reconstruction", pp. 101–110. In Jiang, T., and Lee, D., eds., Lecture Notes in Computer Science, 1276, Springer-Verlag, Berlin. COCOON '97.
  • مشارکت‌کنندگان ویکی‌پدیا، «Neighbor-joining»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد (بازیابی در ۲۵ می ۲۰۱۱).