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

اتصال-همسایگی در بیوانفورماتیک یک روش خوشه بندی پایین به بالا برای ساخت (فنوگرام) است؛ این روش توسط Naruya Saitou و Masatoshi Nei ارائه شده‌است. این روش معمولا برای درختهایی که بر پایه داده‌های توالی دی انی‌ای و پروتئین هستند به کار میرود. این الگوریتم به اطلاعاتی در مورد فاصله بین یک جفت تاگزا(taxa)(گونه‌ها یا توالی‌ها ) در درخت نیاز دارد.
بندانگشتی
توضیح الگوریتم
الگوریتم ابتدا از یک درخت با توپولوژی ستاره مانند شروع می‌شود و پنج مرحله‌ی زیر را تکرار می‌کند تا زمانی که توپولوژی نهایی درخت همراه با طول شاخه‌ها مشخص شوند.
بر اساس ماتریس فاصله‌ها ماتریس Q را که در زیر تعریف می‌شود محاسبه کنید.
جفت تاگزا ای در Q که کمترین مقدار را دارند پیدا کنید. یک گره اضافه کنید که این دو تاگزا را به هم وصل کند.
فاصله‌ی تاگزاهای موجود در این جفت تا گره جدید را محاسبه کنید.
فاصله‌ی تاگزاهای دیگر تا گره جدید را محاسبه کنید.
جفت تاگزای متصل شده به هم را یک تاکسون در نظر بگیرید و با توجه به فواصل جدید به دست آمده مجددا از مرحله‌ی یک الگوریتم را تکرار کنید.
ماتریس Q
بر اساس ماتریس فاصله‌ی بین r تا تاگزا، ماتریس Q را به شکل زیر حساب کنید:
فاصله‌ی بین تاگزاهای i و j است.
فاصله‌ی بین اعضای جفت شده در کد جدید
اگر f و g دو تاکسونی باشند که اخیرا با هم جفت شده‌اند و u گره‌ی جدید باشد، فاصله‌ی f تا u و فاصله‌ی g تا u به صورت زیر محاسبه می‌شوند:
و طبق خاصیت انعکاسی:
فاصله‌ی بین بقیه تاگزاها(taxa)در کد جدید
فاصله‌ی بقیه‌ی تاکسون‌ها تا u توسط فرمول زیر محاسبه می‌شود:
پیچیدگی
اجرای این الگوریتم روی r تاگزا نیاز به 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
C
AB
AB
8
5
0
C
7
0
5
D
0
7
8
در این مثال اگر یکبار دیگر مراحل فوق را روی این ماتریس تکرار کنیم، جواب نهایی حاصل می‌شود.
فواید و مضرات
این روش بر مبنای معیار مینیمم-تکامل استوار است، یعنی، توپولوژی‌ای در هر مرحله انتخاب می‌شود که جمع طول شاخه‌ها در آن کمترین باشد. در نتیجه این الگوریتم یک الگوریتم حریصانه است و ممکن است به جواب درست نرسد.
اما به هرحال این روش در هر مرحله به صورت بهینه عمل می‌کند و در عمل به‌طور معمول دیده شده‌است که درختی که به دست می‌آید به درخت بهینه نزدیک است. اما با این وجود این روش به‌طور گسترده با متدهای فیلوژنتیکی که به فاصله وابسته نیستند و دقیقتر عمل می‌کنند جایگزین شده‌است.
بزرگترین مزیت روش اتصال-همسایگی بر دیگر روش‌ها کارآمد بودن این روش از نظر محاسباتی است زیرا یک الگوریتم چندجمله‌ای است. در نتیجه در مواردی که روش‌های دیگر (مانند: e.g. minimum evolution, maximum parsimony, maximum likelihood) بسیار زمانبر هستند میتوان از این روش استفاده کرد. برخلاف الگوریتم روش جفت گروه بدون وزن با میانگین حسابی در این روش فرض ساعت مولکولی را نداریم یعنی فرض نمی‌کنیم که اجداد با یک نسبت تکامل می‌یابند، بعلاوه درخت حاصل از این روش یک درخت بدون ریشه است؛ هرچند میتوان با استفاده از outgroup این درخت را ریشه دار کرد.
آتسون ثابت کرده‌است که اگر اختلاف هر عنصر در ماتریس فاصله‌ها با فاصله واقعی کمتر از نصف طول کوچکترین شاخه در درخت باشد آنگاه این روش درخت درست را می‌سازد.
و
دو پیاده‌سازی سریع از این روش‌اند.