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

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

توضیح الگوریتم

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

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

ماتریس 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 دو پیاده‌سازی سریع از این روش‌اند.

منابع

↑ 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.

[1] 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.