ในชีวสารสนเทศศาสตร์ Neighbor Joining เป็นวิธี การจัดกลุ่มแบบล่างขึ้นบน (แบบรวมกลุ่ม) สำหรับการสร้างแผนภูมิวิวัฒนาการซึ่งคิดค้นโดย Naruya Saitou และMasatoshi Neiในปี 1987 ^{[ 1 ]}โดยปกติแล้วจะใช้ ข้อมูล ลำดับดีเอ็นเอหรือโปรตีน เป็นพื้นฐาน อัลกอริทึมนี้ต้องการความรู้เกี่ยวกับระยะห่างระหว่างแต่ละคู่ของกลุ่มสิ่งมีชีวิต (เช่น สปีชีส์หรือลำดับ) เพื่อสร้างแผนภูมิวิวัฒนาการ^{[ 2 ]}

การเชื่อมต่อเพื่อนบ้าน (Neighbor joining) รับเมทริกซ์ระยะทางซึ่งระบุระยะทางระหว่างแต่ละคู่ของกลุ่มสิ่งมีชีวิตเป็นอินพุต อัลกอริทึมเริ่มต้นด้วยต้นไม้ที่ยังไม่ได้รับการแก้ไขอย่างสมบูรณ์ ซึ่งมีโครงสร้างทางโทโพโลยีสอดคล้องกับเครือข่ายรูปดาวและทำซ้ำขั้นตอนต่อไปนี้จนกว่าต้นไม้จะได้รับการแก้ไขอย่างสมบูรณ์ และทราบความยาวของกิ่งทั้งหมด:

1. จากเมทริกซ์ระยะทางปัจจุบัน ให้คำนวณเมทริกซ์(ที่กำหนดไว้ด้านล่าง)${\displaystyle Q}$
2. หาคู่ของกลุ่มสิ่งมีชีวิตที่แตกต่างกัน i และ j (เช่น ที่มี) ซึ่งมีค่าน้อยที่สุด สร้างโหนดใหม่ที่เชื่อมกลุ่มสิ่งมีชีวิต i และ j เข้าด้วยกัน และเชื่อมโหนดใหม่เข้ากับโหนดกลาง ตัวอย่างเช่น ในส่วน (B) ของรูปด้านขวา โหนด u ถูกสร้างขึ้นเพื่อเชื่อม f และ g เข้าด้วยกัน${\displaystyle i\neq j}$${\displaystyle Q(i,j)}$
3. คำนวณระยะห่างจากแต่ละกลุ่มอนุกรมวิธานในคู่ไปยังโหนดใหม่นี้
4. คำนวณระยะห่างจากแต่ละกลุ่มอนุกรมวิธานที่อยู่นอกคู่ดังกล่าวไปยังโหนดใหม่
5. เริ่มอัลกอริทึมใหม่อีกครั้ง โดยแทนที่คู่เพื่อนบ้านที่เชื่อมต่อกันด้วยโหนดใหม่ และใช้ระยะทางที่คำนวณได้ในขั้นตอนก่อนหน้า

จากเมทริกซ์ระยะทางที่เชื่อมโยงกลุ่มสิ่งมีชีวิต ให้คำนวณเมทริกซ์x ดังต่อไปนี้: ${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle Q}$

${\displaystyle Q(i,j)=(n-2)d(i,j)-\sum _{k=1}^{n}d(i,k)-\sum _{k=1}^{n}d(j,k)}$

1

ระยะห่างระหว่างกลุ่มสิ่งมีชีวิตและ อยู่ ที่ ใด${\displaystyle d(i,j)}$${\displaystyle i}$${\displaystyle j}$

สำหรับสิ่งมีชีวิตแต่ละชนิดในคู่ที่กำลังจะเชื่อมต่อกัน ให้ใช้สูตรต่อไปนี้ในการคำนวณระยะห่างไปยังโหนดใหม่:

${\displaystyle \delta (f,u)={\frac {1}{2}}d(f,g)+{\frac {1}{2(n-2)}}\left[\sum _{k=1}^{n}d(f,k)-\sum _{k=1}^{n}d(g,k)\right]\quad }$

2

และ:

${\displaystyle \delta (g,u)=d(f,g)-\delta (f,u)\quad }$

Taxa และคือกลุ่มอนุกรมวิธานที่จับคู่กัน และคือโหนดที่สร้างขึ้นใหม่ กิ่งที่เชื่อมและและและและความยาวของกิ่งเหล่านั้นเป็นส่วนหนึ่งของต้นไม้ซึ่งกำลังถูกสร้างขึ้นทีละน้อย โดยกิ่งเหล่านี้จะไม่ส่งผลกระทบหรือได้รับผลกระทบจากขั้นตอนการเชื่อมต่อเพื่อนบ้านในภายหลัง ${\displaystyle f}$${\displaystyle g}$${\displaystyle u}$${\displaystyle f}$${\displaystyle u}$${\displaystyle g}$${\displaystyle u}$${\displaystyle \delta (f,u)}$${\displaystyle \delta (g,u)}$

สำหรับแต่ละกลุ่มสิ่งมีชีวิตที่ไม่ได้พิจารณาในขั้นตอนก่อนหน้า เราจะคำนวณระยะห่างไปยังโหนดใหม่ดังนี้:

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

3

โดยที่โหนดใหม่คือโหนดที่เราต้องการคำนวณระยะทางไป และและคือสมาชิกของคู่ที่เพิ่งเข้าร่วมกัน ${\displaystyle u}$${\displaystyle k}$${\displaystyle f}$${\displaystyle g}$

การเชื่อมต่อเพื่อนบ้านบนชุดของ อนุกรมวิธานต้องใช้การวนซ้ำ ในแต่ละขั้นตอนจะต้องสร้างและค้นหาเมทริกซ์ ในขั้นต้นเมทริกซ์มีขนาดจากนั้นขั้นตอนต่อไปจะมี ขนาด เป็นต้น การนำวิธีนี้ไปใช้โดยตรงจะนำไปสู่อัลกอริทึมที่มีความซับซ้อนของเวลา[ ^{3 ] มีการใช้งานที่ใช้ฮิวริสติกส์เพื่อให้ได้ ผลลัพธ์}ที่ดีกว่านี้โดยเฉลี่ย^{[ 4 ​​]}${\displaystyle n}$${\displaystyle n-3}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle n\times n}$${\displaystyle (n-1)\times (n-1)}$${\displaystyle O(n^{3})}$

สมมติว่าเรามีสิ่งมีชีวิต 5 กลุ่มและมีเมทริกซ์ระยะทางดังต่อไปนี้: ${\displaystyle (a,b,c,d,e)}$${\displaystyle D}$

เราคำนวณค่าโดยใช้สมการ ( 1 ) ตัวอย่างเช่น: ${\displaystyle Q_{1}}$

${\displaystyle Q_{1}(a,b)=(n-2)d(a,b)-\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)}$

${\displaystyle =(5-2)\times 5-(5+9+9+8)-(5+10+10+9)=15-31-34=-50}$

เราได้ค่าต่อไปนี้สำหรับเมทริกซ์ (โดยไม่ใช้ค่าในแนวทแยงของเมทริกซ์และละเว้นไว้ในที่นี้): ${\displaystyle Q_{1}}$

ในตัวอย่างข้างต้นนี่คือค่าที่เล็กที่สุดของดังนั้นเราจึงรวมองค์ประกอบและ เข้าด้วย กัน ${\displaystyle Q_{1}(a,b)=-50}$${\displaystyle Q_{1}}$${\displaystyle a}$${\displaystyle b}$

ให้แทนโหนดใหม่ จากสมการ ( 2 ) ข้างต้น กิ่งที่เชื่อม และกับ จะมีความยาวดังนี้: ${\displaystyle u}$${\displaystyle a}$${\displaystyle b}$${\displaystyle u}$

${\displaystyle \delta (a,u)={\frac {1}{2}}d(a,b)+{\frac {1}{2(5-2)}}\left[\sum _{k=1}^{5}d(a,k)-\sum _{k=1}^{5}d(b,k)\right]\quad ={\frac {5}{2}}+{\frac {31-34}{6}}=2}$

${\displaystyle \delta (b,u)=d(a,b)-\delta (a,u)\quad =5-2=3}$

จากนั้นเราจะดำเนินการอัปเดตเมทริกซ์ระยะทางเริ่มต้นเป็นเมทริกซ์ระยะทางใหม่(ดูด้านล่าง) ซึ่งลดขนาดลงหนึ่งแถวและหนึ่งคอลัมน์เนื่องจากการรวมเข้ากับเพื่อนบ้านโดยใช้สมการ ( 3 ) ข้างต้น เราคำนวณระยะทางจากไปยังโหนดอื่นๆ นอกเหนือจากและในกรณีนี้ เราจะได้: ${\displaystyle D}$${\displaystyle D_{1}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle u}$${\displaystyle u}$${\displaystyle a}$${\displaystyle b}$

${\displaystyle d(u,c)={\frac {1}{2}}[d(a,c)+d(b,c)-d(a,b)]={\frac {9+10-5}{2}}=7}$

${\displaystyle d(u,d)={\frac {1}{2}}[d(a,d)+d(b,d)-d(a,b)]={\frac {9+10-5}{2}}=7}$

${\displaystyle d(u,e)={\frac {1}{2}}[d(a,e)+d(b,e)-d(a,b)]={\frac {8+9-5}{2}}=6}$

เมทริกซ์ระยะทางที่ได้คือ: ${\displaystyle D_{1}}$

ค่าที่เป็นตัวหนาแสดงถึงระยะทางที่คำนวณใหม่ ในขณะที่ค่าที่เป็นตัวเอียงจะไม่ได้รับผลกระทบจากการอัปเดตเมทริกซ์ เนื่องจากเป็นระยะทางระหว่างองค์ประกอบที่ไม่เกี่ยวข้องกับการเชื่อมต่อกลุ่มสิ่งมีชีวิตในครั้งแรก ${\displaystyle D_{1}}$

เมทริกซ์ ที่เกี่ยวข้องคือ: ${\displaystyle Q_{2}}$

เราอาจเลือกที่จะเชื่อมต่อและหรือเชื่อมต่อและก็ได้ ทั้งสองคู่มีค่าต่ำสุดของและไม่ว่าจะเลือกแบบใดก็จะได้ผลลัพธ์เดียวกัน เพื่อความชัดเจน เราจะเชื่อมต่อและและเรียกโหนดใหม่ว่า ${\displaystyle u}$${\displaystyle c}$${\displaystyle d}$${\displaystyle e}$${\displaystyle Q_{2}}$${\displaystyle -28}$${\displaystyle u}$${\displaystyle c}$${\displaystyle v}$

สามารถคำนวณ ความยาวของกิ่งที่เชื่อมต่อ และไปยังได้ :${\displaystyle u}$${\displaystyle c}$${\displaystyle v}$

${\displaystyle \delta (u,v)={\frac {1}{2}}d(u,c)+{\frac {1}{2(4-2)}}\left[\sum _{k=1}^{4}d(u,k)-\sum _{k=1}^{4}d(c,k)\right]\quad ={\frac {7}{2}}+{\frac {20-22}{4}}=3}$

${\displaystyle \delta (c,v)=d(u,c)-\delta (u,v)\quad =7-3=4}$

การเชื่อมต่อองค์ประกอบและการคำนวณความยาวของกิ่งช่วยในการวาดแผนผังการเชื่อมต่อเพื่อนบ้าน ดัง แสดง ในรูป

ขณะนี้ได้คำนวณ เมทริกซ์ระยะทางที่อัปเดตแล้วสำหรับโหนดที่เหลืออีก 3 โหนด ได้แก่, , และแล้ว: ${\displaystyle D_{2}}$${\displaystyle v}$${\displaystyle d}$${\displaystyle e}$

${\displaystyle d(v,d)={\frac {1}{2}}[d(u,d)+d(c,d)-d(u,c)]={\frac {7+8-7}{2}}=4}$

${\displaystyle d(v,e)={\frac {1}{2}}[d(u,e)+d(c,e)-d(u,c)]={\frac {6+7-7}{2}}=3}$

ในขั้นตอนนี้ โครงสร้างของต้นไม้ได้รับการแก้ไขอย่างสมบูรณ์แล้ว อย่างไรก็ตาม เพื่อความชัดเจน เราสามารถคำนวณเมทริกซ์ได้ ตัวอย่างเช่น: ${\displaystyle Q_{3}}$

${\displaystyle Q_{3}(v,e)=(3-2)d(v,e)-\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(e,k)=3-7-6=-10}$

เพื่อให้เห็นภาพชัดเจนยิ่งขึ้น เราจะเชื่อมต่อและและเรียกโหนดสุดท้ายว่าความยาวของกิ่งที่เหลืออีกสามกิ่งสามารถคำนวณได้ดังนี้: ${\displaystyle v}$${\displaystyle d}$${\displaystyle w}$

${\displaystyle \delta (v,w)={\frac {1}{2}}d(v,d)+{\frac {1}{2(3-2)}}\left[\sum _{k=1}^{3}d(v,k)-\sum _{k=1}^{3}d(d,k)\right]\quad ={\frac {4}{2}}+{\frac {7-7}{2}}=2}$

${\displaystyle \delta (w,d)=d(v,d)-\delta (v,w)=4-2=2}$

${\displaystyle \delta (w,e)=d(v,e)-\delta (v,w)=3-2=1}$

โครงสร้างต้นไม้การเชื่อมต่อเพื่อนบ้าน (Neighbor Joining Tree ) เสร็จสมบูรณ์แล้วดังแสดงในรูป

ตัวอย่างนี้แสดงถึงกรณีในอุดมคติ: โปรดสังเกตว่า หากเราเคลื่อนที่จากกลุ่มอนุกรมวิธานใด ๆ ไปยังกลุ่มอนุกรมวิธานอื่น ๆ ตามกิ่งก้านของต้นไม้ และรวมความยาวของกิ่งก้านที่เคลื่อนที่ผ่าน ผลลัพธ์จะเท่ากับระยะทางระหว่างกลุ่มอนุกรมวิธานเหล่านั้นในเมทริกซ์ระยะทางที่ป้อนเข้ามา ตัวอย่างเช่น จาก ไปยังเราจะได้เมทริกซ์ระยะทางที่มีระยะทางสอดคล้องกับต้นไม้บางต้นในลักษณะนี้เรียกว่า 'เมทริกซ์บวก' ซึ่งเป็นคุณสมบัติที่หายากในทางปฏิบัติ เมื่อกำหนดเมทริกซ์ระยะทางบวกเป็นอินพุต การเชื่อมต่อเพื่อนบ้านจะรับประกันได้ว่าจะพบต้นไม้ที่มีระยะทางระหว่างกลุ่มอนุกรมวิธานสอดคล้องกับเมทริกซ์นั้น ${\displaystyle d}$${\displaystyle b}$${\displaystyle 2+2+3+3=10}$

การเชื่อมต่อเพื่อนบ้านอาจถูกมองว่าเป็นฮิวริสติกแบบโลภสำหรับ เกณฑ์ วิวัฒนาการขั้นต่ำที่สมดุล^{[ 5 ]} (BME) สำหรับแต่ละโทโพโลยี BME กำหนดความยาวของต้นไม้ (ผลรวมของความยาวกิ่ง) ให้เป็นผลรวมถ่วงน้ำหนักเฉพาะของระยะทางในเมทริกซ์ระยะทาง โดยน้ำหนักจะขึ้นอยู่กับโทโพโลยี โทโพโลยีที่เหมาะสมที่สุดของ BME คือโทโพโลยีที่ลดความยาวของต้นไม้นี้ให้เหลือน้อยที่สุด NJ ในแต่ละขั้นตอนจะเชื่อมต่อคู่ของแท็กซาอย่างโลภซึ่งจะทำให้ความยาวของต้นไม้ที่ประมาณไว้ลดลงมากที่สุด ขั้นตอนนี้ไม่รับประกันว่าจะพบค่าที่เหมาะสมที่สุดสำหรับเกณฑ์ BME แม้ว่าจะพบบ่อยครั้งและมักจะค่อนข้างใกล้เคียง^{[ 5 ]}

ข้อดีหลักของ NJ คือความเร็ว^{[ 6 ] : 466} เมื่อเปรียบเทียบกับวิธีleast squares , maximum parsimonyและmaximum likelihood ^{[ 6 ]} ทำให้สามารถวิเคราะห์ชุดข้อมูลขนาดใหญ่ได้ (หลายร้อยหรือหลายพัน taxa) และสำหรับการบูตสแตรปปิ้งซึ่งวิธีการวิเคราะห์อื่นๆ (เช่นmaximum parsimony , maximum likelihood ) อาจมีข้อจำกัด ด้านการคำนวณ

การเชื่อมต่อเพื่อนบ้านมีคุณสมบัติที่ว่า หากเมทริกซ์ระยะทางอินพุตถูกต้อง ต้นไม้เอาต์พุตก็จะถูกต้องเช่นกัน ยิ่งไปกว่านั้น ความถูกต้องของโทโพโลยีต้นไม้เอาต์พุตจะได้รับการรับประกันตราบใดที่เมทริกซ์ระยะทางเป็นแบบ 'เกือบบวก' โดยเฉพาะอย่างยิ่งหากแต่ละรายการในเมทริกซ์ระยะทางแตกต่างจากระยะทางจริงน้อยกว่าครึ่งหนึ่งของความยาวกิ่งที่สั้นที่สุดในต้นไม้^{[ 7 ]} ในทางปฏิบัติ เมทริกซ์ระยะทางแทบจะไม่ตรงตามเงื่อนไขนี้ แต่การเชื่อมต่อเพื่อนบ้านมักจะสร้างโทโพโลยีต้นไม้ที่ถูกต้องอยู่ดี^{[ 8 ]}ความถูกต้องของการเชื่อมต่อเพื่อนบ้านสำหรับเมทริกซ์ระยะทางแบบเกือบบวกหมายความว่ามีความสอดคล้องทางสถิติภายใต้แบบจำลองวิวัฒนาการหลายแบบ เมื่อมีข้อมูลที่มีความยาวเพียงพอ การเชื่อมต่อเพื่อนบ้านจะสร้างต้นไม้จริงขึ้นมาใหม่ด้วยความน่าจะเป็นสูง เมื่อเปรียบเทียบกับUPGMAและWPGMAการเชื่อมต่อเพื่อนบ้านมีข้อได้เปรียบตรงที่ไม่ถือว่าสายพันธุ์ทั้งหมดวิวัฒนาการในอัตราเดียวกัน ( สมมติฐานนาฬิกาโมเลกุล )

อย่างไรก็ตาม วิธีการเชื่อมต่อเพื่อนบ้าน (Neighbor joining) ได้ถูกแทนที่ด้วยวิธีการทางวิวัฒนาการที่ไม่ต้องอาศัยการวัดระยะทางและให้ความแม่นยำสูงกว่าในเกือบทุกกรณีแล้ว ข้อเสียของวิธีการเชื่อมต่อเพื่อนบ้านคือ มักจะกำหนดความยาวติดลบให้กับบางกิ่ง

มีโปรแกรมมากมายที่ใช้การเชื่อมต่อเพื่อนบ้าน (neighbor joining) ในบรรดาการใช้งาน NJ แบบมาตรฐาน (เช่น การใช้เกณฑ์การเพิ่มประสิทธิภาพ NJ แบบคลาสสิก ดังนั้นจึงให้ผลลัพธ์เดียวกัน) RapidNJ (เริ่มในปี 2003 อัปเดตครั้งใหญ่ในปี 2011 และยังคงอัปเดตในปี 2023) ^{[ 9 ]}และ NINJA (เริ่มในปี 2009 อัปเดตครั้งสุดท้ายในปี 2013) ^{[ 10 ]}ถือเป็นโปรแกรมที่ทันสมัยที่สุด โดยทั่วไปแล้วเวลาในการทำงานจะแปรผันตามกำลังสองของจำนวนแท็กซาโดยประมาณ

รูปแบบที่เบี่ยงเบนจากรูปแบบมาตรฐาน ได้แก่:

• BIONJ (1997) ^{[ 11 ]}และ Weighbor (2000) ^{[ 12 ]}ปรับปรุงความแม่นยำโดยใช้ประโยชน์จากข้อเท็จจริงที่ว่าระยะทางที่สั้นกว่าในเมทริกซ์ระยะทางโดยทั่วไปจะทราบได้ดีกว่าระยะทางที่ยาวกว่า วิธีการทั้งสองได้รับการขยายให้ทำงานบนเมทริกซ์ระยะทางที่ไม่สมบูรณ์^{[ 13 ]}
• "Fast NJ" จดจำโหนดที่ดีที่สุดและมีความซับซ้อน O(n^2) เสมอ "relax NJ" ดำเนินการค้นหาแบบปีนเขาและรักษาความซับซ้อนในกรณีที่เลวร้ายที่สุดไว้ที่ O(n^3) Rapid NJ เร็วกว่า relaxed NJ ทั่วไป^{[ 14 ]}
• FastME เป็นการนำ วิธี การวิวัฒนาการขั้นต่ำแบบสมดุล (BME) ที่เกี่ยวข้องอย่างใกล้ชิดมาใช้ (ดู§ การเชื่อมต่อเพื่อนบ้านเป็นวิวัฒนาการขั้นต่ำ ) มีความเร็วและความแม่นยำใกล้เคียงกับ NJ โดยเริ่มต้นจากต้นไม้แบบคร่าวๆ แล้วปรับปรุงโดยใช้ชุดการเคลื่อนไหวเชิงโทโพโลยี เช่น การแลกเปลี่ยนเพื่อนบ้านที่ใกล้ที่สุด (NNI) ^{[ 15 ]} FastTree เป็นวิธีการที่เกี่ยวข้อง โดยทำงานกับ "โปรไฟล์" ของลำดับแทนที่จะเป็นเมทริกซ์ เริ่มต้นด้วยต้นไม้ NJ โดยประมาณ จัดเรียงใหม่เป็น BME จากนั้นจัดเรียงใหม่เป็นความน่าจะเป็นสูงสุดโดยประมาณ^{[ 16 ]}

• การค้นหาเพื่อนบ้านที่ใกล้ที่สุด
• UPGMAและWPGMA
• วิวัฒนาการขั้นต่ำ

• วิธี Neighbor-Joining ถูกเก็บถาวรไว้เมื่อวันที่ 9 กรกฎาคม 2021 ที่Wayback Machine — บทแนะนำ