ในคณิตศาสตร์วิทยาศาสตร์คอมพิวเตอร์และโดยเฉพาะอย่างยิ่งทฤษฎีกราฟเมทริกซ์ระยะทางคือเมทริกซ์จัตุรัส (อาร์เรย์สองมิติ) ที่ประกอบด้วยระยะทางที่คำนวณเป็นคู่ๆ ระหว่างองค์ประกอบของเซต^{[ 1 ]}ขึ้นอยู่กับการใช้งานที่เกี่ยวข้อง "ระยะทาง" ที่ใช้ในการกำหนดเมทริกซ์นี้อาจเป็นเมตริก หรือไม่ก็ได้ หากมี องค์ประกอบ Nตัว เมทริกซ์นี้จะมีขนาดN × Nในการใช้งานทางทฤษฎีกราฟ องค์ประกอบมักจะเรียกว่าจุด โหนด หรือจุดยอด

โดยทั่วไป เมทริกซ์ระยะทางคือเมทริกซ์ประชิดแบบถ่วง น้ำหนัก ของกราฟบางกราฟ ในเครือข่าย ซึ่ง เป็นกราฟแบบมีทิศทางที่มีการกำหนดน้ำหนักให้กับส่วนโค้ง ระยะทางระหว่างโหนดสองโหนดของเครือข่ายสามารถกำหนดได้เป็นค่าต่ำสุดของผลรวมของน้ำหนักบนเส้นทางที่สั้นที่สุดที่เชื่อมระหว่างโหนดทั้งสอง (โดยที่จำนวนขั้นตอนในเส้นทางมีขอบเขตจำกัด) ^{[ 2 ]}ฟังก์ชันระยะทางนี้ แม้ว่าจะกำหนดไว้อย่างดี แต่ก็ไม่ใช่เมตริก ไม่จำเป็นต้องมีข้อจำกัดใดๆ เกี่ยวกับน้ำหนัก นอกเหนือจากความจำเป็นในการรวมและเปรียบเทียบน้ำหนัก ดังนั้นจึงมีการใช้น้ำหนักติดลบในบางแอปพลิเคชัน เนื่องจากเส้นทางมีทิศทาง จึงไม่สามารถรับประกันความสมมาตรได้ และหากมีวงจรที่มีน้ำหนักติดลบ เมทริกซ์ระยะทางอาจไม่กลวง (และในกรณีที่ไม่มีขอบเขตจำกัดของจำนวนขั้นตอน เมทริกซ์อาจไม่มีนิยาม)

สามารถกำหนดสูตรทางพีชคณิตของสิ่งข้างต้นได้โดยใช้พีชคณิต min-plusการคูณเมทริกซ์ในระบบนี้กำหนดไว้ดังนี้: กำหนดให้ เมทริกซ์ n × n สอง เมทริกซ์A = ( a _ij )และB = ( b _ij )ผลคูณระยะทางC = ( c _ij ) = A ⭑ Bถูกกำหนดให้เป็น เมทริกซ์ n × nเช่นนั้น

${\displaystyle c_{ij}=\min _{k=1}^{n}\{a_{ik}+b_{kj}\}.}$

โปรดทราบว่าองค์ประกอบนอกแนวทแยงมุมที่ไม่เชื่อมต่อโดยตรงจะต้องตั้งค่าเป็นอนันต์หรือค่าขนาดใหญ่ที่เหมาะสมเพื่อให้การดำเนินการ min-plus ทำงานได้อย่างถูกต้อง การกำหนดค่าเป็นศูนย์ในตำแหน่งเหล่านี้จะถูกตีความผิดพลาดว่าเป็นขอบที่ไม่มีระยะทาง ต้นทุน ฯลฯ

ถ้าWคือ เมทริกซ์ n × nที่ประกอบด้วยน้ำหนักของขอบในกราฟW ^k (โดยใช้ผลคูณระยะทางนี้) จะให้ระยะทางระหว่างจุดยอดโดยใช้เส้นทางที่มีความยาวไม่เกินk ขอบและเมทริกซ์ระยะทางนี้จะเป็นเมทริกซ์ระยะทางของกราฟเมื่อกำหนดขอบเขตจำนวนขั้นตอนเป็นkถ้าไม่มีวงวนที่มีน้ำหนักติดลบW ⁿจะให้เมทริกซ์ระยะทางที่แท้จริงโดยไม่มีขอบเขต เพราะการลบจุดยอดที่ซ้ำกันออกจากเส้นทางไม่สามารถลดน้ำหนักของเส้นทางนั้นได้ ในทางกลับกัน ถ้าiและjอยู่ในวงวนที่มีน้ำหนักติดลบW ^k _ijจะลดลงอย่างไม่มีขอบเขตเมื่อkเพิ่มขึ้น

กราฟG ใดๆ ที่มีnจุดยอด สามารถจำลองได้เป็นกราฟสมบูรณ์แบบ มีน้ำหนัก ที่มีnจุดยอด โดยกำหนดน้ำหนักหนึ่งให้กับขอบแต่ละขอบของกราฟสมบูรณ์ที่สอดคล้องกับขอบของGและกำหนดน้ำหนักอนันต์ให้กับขอบอื่นๆ ทั้งหมดWสำหรับกราฟสมบูรณ์นี้คือเมทริกซ์ประชิดของGเมทริกซ์ระยะทางของGสามารถคำนวณได้จากWดังที่กล่าวมาข้างต้น ในทางตรงกันข้าม หากใช้การคูณเมทริกซ์แบบปกติ และจุดยอดที่ไม่ได้เชื่อมโยงกันถูกแทนด้วย 0 Wnจะเข้ารหัสจำนวนเส้นทางระหว่างจุดยอดสองจุดใดๆ ที่มีความยาว^{เท่ากับ} nแทน

คุณค่าของรูปแบบเมทริกซ์ระยะทางในหลายๆ การประยุกต์ใช้ อยู่ที่ว่าเมทริกซ์ระยะทางสามารถเข้ารหัสสัจพจน์เมตริก ได้อย่างชัดเจน และเอื้อต่อการใช้เทคนิคพีชคณิตเชิงเส้นอย่างไร กล่าวคือ ถ้าM = ( x _ij )โดยที่1 ≤ i , j ≤ Nเป็นเมทริกซ์ระยะทางสำหรับระยะทางเมตริกแล้ว

1. ค่าในแนวทแยงมุมหลักทั้งหมดเป็นศูนย์ (นั่นคือ เมทริกซ์เป็นเมทริกซ์กลวง ) กล่าวคือx _ii = 0สำหรับทุก1 ≤ i ≤ N
2. ค่าในแนวทแยงมุมทั้งหมดเป็นค่าบวก ( x _ij > 0ถ้าi ≠ j ) (กล่าวคือ เป็นเมทริกซ์ที่ไม่เป็นลบ )
3. เมทริกซ์ดังกล่าวเป็นเมทริกซ์สมมาตร ( x _ij = x _ji ) และ
4. สำหรับiและj ใดๆ x _ij ≤ x ik + x _kjสำหรับk ทุกตัว (อสมการสามเหลี่ยม) สามารถกล่าวได้ในรูปของ_การคูณเมทริกซ์ทรอปิคอล

เมื่อเมทริกซ์ระยะทางเป็นไปตามสัจพจน์สามข้อแรก (ทำให้มันเป็นเมทริกซ์กึ่งเมตริก) บางครั้งจะเรียกว่าเมทริกซ์ระยะทางเบื้องต้น เมทริกซ์ระยะทางเบื้องต้นที่สามารถฝังอยู่ในปริภูมิยูคลิดได้เรียกว่าเมทริกซ์ระยะทางยูคลิดสำหรับข้อมูลประเภทผสมที่มีทั้งตัวบ่งชี้เชิงตัวเลขและเชิงหมวดหมู่ ระยะทางของ Gowerเป็นทางเลือกที่นิยมใช้กัน

อีกตัวอย่างหนึ่งที่พบได้ทั่วไปของเมทริกซ์ระยะทางเมตริกเกิดขึ้นในทฤษฎีการเข้ารหัสเมื่อในรหัสบล็อกองค์ประกอบต่างๆ เป็นสตริงที่มีความยาวคงที่บนตัวอักษร และระยะทางระหว่างองค์ประกอบเหล่านั้นกำหนดโดย เมตริก ระยะทางแฮมมิง ค่าที่ไม่เป็นศูนย์ที่เล็กที่สุดในเมทริกซ์ระยะทางจะวัดความสามารถในการแก้ไขข้อผิดพลาดและการตรวจจับข้อผิดพลาดของรหัส

เมทริกซ์ระยะทางแบบบวก (Additive distance matrix) เป็นเมทริกซ์ชนิดพิเศษที่ใช้ในชีวสารสนเทศเพื่อสร้างแผนภูมิวิวัฒนาการให้xเป็นบรรพบุรุษร่วมที่ต่ำที่สุดระหว่างสองสปีชีส์iและjเราคาดหวังว่าM _ij = M _ix + M _xjนี่คือที่มาของเมตริกแบบบวก เมทริกซ์ระยะทางMสำหรับเซตของสปีชีส์Sจะเรียกว่าเป็นแบบบวกก็ต่อเมื่อมีแผนภูมิวิวัฒนาการTสำหรับSอยู่จริง โดยที่:

• ขอบทุกเส้น( u , v )ในTจะสัมพันธ์กับน้ำหนักบวกd _uv
• สำหรับทุกi , j ∈ S , M _ijจะเท่ากับผลรวมของน้ำหนักตามเส้นทางจากiไปยังjใน T

ในกรณีนี้Mเรียกว่าเมทริกซ์แบบบวก และTเรียกว่าต้นไม้แบบบวก ด้านล่างนี้เป็นตัวอย่างของเมทริกซ์ระยะทางแบบบวกและต้นไม้ที่สอดคล้องกัน:

เมทริกซ์ระยะทางอัลตราเมตริกถูกนิยามว่าเป็นเมทริกซ์แบบบวกซึ่งจำลองนาฬิกาโมเลกุล คง ที่ ใช้ในการสร้างแผนภูมิวิวัฒนาการ เมทริกซ์Mเรียกว่าเป็นเมทริกซ์อัลตราเมตริก ถ้ามีแผนภูมิวิวัฒนาการT ที่มี คุณสมบัติดังต่อไปนี้:

• M _ijเท่ากับผลรวมของน้ำหนักขอบตามเส้นทางจากiไปยังjในT
• รากของต้นไม้สามารถระบุได้จากระยะห่างระหว่างรากกับใบทุกใบที่เท่ากัน

ต่อไปนี้เป็นตัวอย่างของเมทริกซ์ระยะทางอัลตราเมตริกพร้อมแผนผังต้นไม้ที่เกี่ยวข้อง:

เมทริกซ์ระยะทางถูกนำมาใช้กันอย่างแพร่หลายในสาขาชีวสารสนเทศ และปรากฏอยู่ในวิธีการ อัลกอริทึม และโปรแกรมหลายอย่าง เมทริกซ์ระยะทางใช้เพื่อแสดง โครงสร้าง โปรตีนในลักษณะที่ไม่ขึ้นกับพิกัด รวมถึงระยะทางระหว่างคู่ของลำดับสองลำดับในพื้นที่ลำดับมีการใช้ใน การจัดเรียง โครงสร้างและลำดับและสำหรับการกำหนดโครงสร้างโปรตีนจากNMRหรือ การ ตกผลึก ด้วยรังสีเอกซ์

บางครั้ง การแสดงข้อมูลในรูปแบบเมท ริก ซ์ความคล้ายคลึงกันนั้นสะดวกกว่า

นอกจากนี้ยังใช้เพื่อกำหนดความสัมพันธ์เชิงระยะทางด้วย

การจัดเรียงลำดับสองลำดับเกิดขึ้นจากการแทรกช่องว่างในตำแหน่งที่กำหนดตามลำดับเพื่อให้ได้ความยาวเท่ากันและไม่มีช่องว่างสองช่องที่ตำแหน่งเดียวกันของลำดับที่เพิ่มเข้ามาทั้งสอง^{[ 3 ]}หนึ่งในวิธีการหลักสำหรับการจัดเรียงลำดับคือการเขียนโปรแกรมแบบไดนามิกวิธีนี้ใช้ในการเติมเมทริกซ์ระยะทางแล้วจึงได้การจัดเรียง ในการใช้งานทั่วไปสำหรับการจัดเรียงลำดับจะใช้เมทริกซ์เพื่อกำหนดคะแนนให้กับการจับคู่หรือการไม่ตรงกันของกรดอะมิโน และค่าปรับสำหรับช่องว่างที่ตรงกับกรดอะมิโนในลำดับหนึ่งกับช่องว่างในอีกลำดับหนึ่ง

อัลกอริทึม Needleman –Wunschที่ใช้ในการคำนวณการจัดเรียงทั่วโลกนั้นใช้การเขียนโปรแกรมเชิงพลวัตเพื่อสร้างเมทริกซ์ระยะทาง

อัลกอริทึม Smith–Watermanก็เป็นอัลกอริทึมที่ใช้การเขียนโปรแกรมเชิงพลวัตเช่นกัน ซึ่งประกอบด้วยการหาเมทริกซ์ระยะทางแล้วจึงหาการจัดเรียงในระดับท้องถิ่น

การจัดเรียงลำดับหลายลำดับพร้อมกัน (Multiple sequence alignment: MSA)เป็นส่วนขยายของการจัดเรียงลำดับแบบคู่ (Pairwise alignment) เพื่อจัดเรียงลำดับหลายลำดับพร้อมกัน วิธีการ MSA ที่แตกต่างกันนั้นใช้หลักการเดียวกันคือเมทริกซ์ระยะทาง เช่นเดียวกับการจัดเรียงลำดับแบบทั่วโลกและแบบเฉพาะที่

• วิธีการหาจุดศูนย์กลาง (Center star method) วิธีนี้กำหนดลำดับศูนย์กลางS _cซึ่งทำให้ระยะห่างระหว่างลำดับS _cกับลำดับอื่นๆS _i มีค่าน้อยที่สุด จากนั้นจะสร้างการจัดเรียงหลายลำดับ (Multiple alignment ) MสำหรับชุดลำดับSโดยที่สำหรับทุกS _iระยะห่างในการจัดเรียงd _M ( S _c , S _i )คือการจัดเรียงแบบคู่ที่ดีที่สุด วิธีนี้มีลักษณะเฉพาะคือ การจัดเรียงที่คำนวณได้สำหรับSซึ่งผลรวมของระยะห่างแบบคู่มีค่าไม่เกินสองเท่าของการจัดเรียงหลายลำดับที่ดีที่สุด
• วิธีการจัดเรียงลำดับแบบก้าวหน้า (Progressive alignment method) วิธีการเชิงฮิวริสติกนี้ใช้ในการสร้าง MSA โดยเริ่มจากการจัดเรียงลำดับสองลำดับที่มีความสัมพันธ์กันมากที่สุดก่อน จากนั้นจึงจัดเรียงลำดับสองลำดับถัดไปที่มีความสัมพันธ์กันมากที่สุดไปเรื่อยๆ จนกว่าจะจัดเรียงลำดับทั้งหมดเสร็จ

นอกจากนี้ยังมีวิธีการอื่นๆ ที่มีโปรแกรมเฉพาะของตัวเองเนื่องจากได้รับความนิยม:

• คลัสทัลดับเบิลยู
• กล้ามเนื้อ
• แมฟท์
• มะม่วง
• และอีกมากมาย

โปรแกรมจัดเรียงลำดับหลายลำดับโดยใช้การแปลงฟูริเยร์แบบเร็ว (MAFFT) เป็นโปรแกรมที่มีอัลกอริทึมที่ใช้การจัดเรียงลำดับแบบก้าวหน้า และมีกลยุทธ์การจัดเรียงลำดับหลายลำดับที่หลากหลาย ขั้นแรก MAFFT จะสร้างเมทริกซ์ระยะทางโดยอิงจากจำนวน 6-tuple ที่ใช้ร่วมกัน ขั้นที่สอง มันจะสร้างต้นไม้แนะนำโดยอิงจากเมทริกซ์ก่อนหน้า ขั้นที่สาม มันจะจัดกลุ่มลำดับโดยใช้การแปลงฟูริเยร์แบบเร็วและเริ่มการจัดเรียงลำดับ โดยอิงจากการจัดเรียงลำดับใหม่ มันจะสร้างต้นไม้แนะนำขึ้นใหม่และจัดเรียงลำดับอีกครั้ง

ในการ วิเคราะห์ความสัมพันธ์ ทางวิวัฒนาการขั้นตอนแรกคือการสร้างแผนภูมิวิวัฒนาการ: เมื่อมีกลุ่มของสิ่งมีชีวิตแล้ว ปัญหาคือการสร้างหรืออนุมานความสัมพันธ์ทางบรรพบุรุษระหว่างสิ่งมีชีวิตเหล่านั้น กล่าวคือ แผนภูมิวิวัฒนาการระหว่างสิ่งมีชีวิต วิธีการเมทริกซ์ระยะทางจะดำเนินการกิจกรรมนี้

วิธีเมทริกซ์ระยะทางในการวิเคราะห์ทางวิวัฒนาการอาศัยการวัด "ระยะทางทางพันธุกรรม" ระหว่างลำดับที่กำลังจัดประเภทอย่างชัดเจน ดังนั้นจึงต้องใช้ลำดับหลายลำดับเป็นอินพุต วิธีการระยะทางพยายามสร้างเมทริกซ์แบบ all-to-all จากชุดลำดับแบบสอบถามที่อธิบายระยะทางระหว่างแต่ละคู่ลำดับ จากนั้นจึงสร้างแผนภูมิวิวัฒนาการที่วางลำดับที่เกี่ยวข้องอย่างใกล้ชิดไว้ภายใต้โหนดภายใน เดียวกัน และความยาวของกิ่งจะจำลองระยะทางที่สังเกตได้ระหว่างลำดับได้อย่างใกล้เคียง วิธีการเมทริกซ์ระยะทางอาจสร้างแผนภูมิแบบมีรากหรือไม่มีรากก็ได้ ขึ้นอยู่กับอัลกอริทึมที่ใช้ในการคำนวณ^{[ 4 ]}เมื่อมี nสปีชีส์ อินพุตคือเมทริกซ์ระยะทางn × n Mโดยที่M _ijคือระยะทางการกลายพันธุ์ระหว่างสปีชีส์iและjเป้าหมายคือการส่งออกแผนภูมิที่มีดีกรี3ซึ่งสอดคล้องกับเมทริกซ์ระยะทาง

มักใช้เป็นพื้นฐานสำหรับการจัดเรียงลำดับหลายลำดับ แบบก้าวหน้าและแบบวนซ้ำ ข้อเสียหลักของวิธีการเมทริกซ์ระยะทางคือไม่สามารถใช้ข้อมูลเกี่ยวกับภูมิภาคที่มีความแปรผันสูงในท้องถิ่นที่ปรากฏในหลายซับทรีได้อย่างมี ประสิทธิภาพ ^{[ 4 ]}แม้จะมีปัญหาที่อาจเกิดขึ้น วิธีการระยะทางก็รวดเร็วมาก และมักให้ค่าประมาณของวิวัฒนาการที่สมเหตุสมผล นอกจากนี้ยังมีข้อดีบางประการเหนือวิธีการที่ใช้ลักษณะโดยตรง ที่สำคัญ วิธีการระยะทางช่วยให้สามารถใช้ข้อมูลที่อาจไม่สามารถแปลงเป็นข้อมูลลักษณะได้ง่าย เช่นการทดสอบ การผสมพันธุ์ DNA–DNA

ต่อไปนี้เป็นวิธีการสร้างแผนภูมิวิวัฒนาการโดยอิงตามระยะทาง:

• การสร้างต้นไม้แบบเพิ่ม
• อุจีเอ็มเอ
• เพื่อนบ้านเข้าร่วม
• ฟิตช์-มาร์โกเลียช

การสร้างแผนภูมิต้นไม้แบบบวกนั้นอาศัยเมทริกซ์ระยะทางแบบบวกและแบบอัลตราเมตริก เมทริกซ์เหล่านี้มีลักษณะพิเศษดังนี้:

พิจารณาเมทริกซ์บวกMสำหรับสามชนิดใดๆi, j, kต้นไม้ที่สอดคล้องกันจะมีเอกลักษณ์เฉพาะ^{[ 3 ]}เมทริกซ์ระยะทางอัลตราเมตริกทุกเมทริกซ์เป็นเมทริกซ์บวก เราสามารถสังเกตคุณสมบัตินี้ได้สำหรับต้นไม้ด้านล่าง ซึ่งประกอบด้วยชนิดi, j, k

เทคนิคการสร้างต้นไม้แบบเพิ่มค่าเริ่มต้นด้วยต้นไม้ต้นนี้ จากนั้นจึงเพิ่มชนิดพันธุ์อีกหนึ่งชนิดในแต่ละครั้ง โดยพิจารณาจากเมทริกซ์ระยะทางร่วมกับคุณสมบัติที่กล่าวถึงข้างต้น ตัวอย่างเช่น พิจารณาเมทริกซ์แบบเพิ่มค่าMและชนิดพันธุ์ 5 ชนิด ได้แก่a , b , c , dและeขั้นแรก เราสร้างต้นไม้แบบเพิ่มค่าสำหรับชนิดพันธุ์aและb สองชนิด จากนั้นเราเลือกชนิดพันธุ์ที่สาม สมมติว่าเป็นcและเชื่อมต่อเข้ากับจุดxบนขอบระหว่างaและbน้ำหนักของขอบจะถูกคำนวณโดยใช้คุณสมบัติข้างต้น ต่อไปเราเพิ่มชนิดพันธุ์ที่สี่dเข้ากับขอบใดก็ได้ หากเราใช้คุณสมบัติ เราจะระบุได้ว่าdควรเชื่อมต่อกับขอบเฉพาะเพียงขอบเดียวเท่านั้น สุดท้าย เราเพิ่มeโดยทำตามขั้นตอนเดียวกันกับก่อนหน้านี้

หลักการพื้นฐานของ UPGMA (Unweighted Pair Group Method with Arithmetic Mean) คือ สปีชีส์ที่คล้ายคลึงกันควรอยู่ใกล้กันในแผนภูมิวิวัฒนาการ ดังนั้นจึงสร้างแผนภูมิโดยการจัดกลุ่มลำดับที่คล้ายคลึงกันซ้ำๆ วิธีนี้ทำงานโดยการสร้างแผนภูมิวิวัฒนาการจากล่างขึ้นบนจากใบของมัน ในขั้นต้น เรามี ใบ nใบ (หรือต้นไม้เดี่ยวn ​​ต้น) แต่ละใบแทนสปีชีส์ใน S ใบ n ใบ เหล่านั้นเรียกว่า คลัสเตอร์ nกลุ่ม จากนั้นเราทำการวน ซ้ำ n -1 ครั้ง ในแต่ละรอบ เรา _จะระบุคลัสเตอร์สองกลุ่มC1และC2 ที่มีระยะห่างเฉลี่ยน้อยที่สุดและรวมเข้า _ด้วยกันเพื่อสร้างคลัสเตอร์ที่ใหญ่กว่าC2หากเราสมมติว่าMเป็นอัลตราเมตริก สำหรับคลัสเตอร์C ใดๆ ที่สร้างขึ้นโดยอัลกอริทึม UPGMA นั้นC2เป็นต้นไม้แบบอัลตราเมตริกที่ถูกต้อง

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

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

วิธี Fitch–Margoliash ใช้ระเบียบวิธีถ่วงน้ำหนักกำลังสองน้อยที่สุดสำหรับการจัดกลุ่มตามระยะทางทางพันธุกรรม ลำดับที่มีความสัมพันธ์ใกล้ชิดกันจะได้รับน้ำหนักมากขึ้นในกระบวนการสร้างต้นไม้เพื่อแก้ไขความไม่แม่นยำที่เพิ่มขึ้นในการวัดระยะทางระหว่างลำดับที่มีความสัมพันธ์ห่างไกลกัน เกณฑ์กำลังสองน้อยที่สุดที่ใช้กับระยะทางเหล่านี้มีความแม่นยำมากขึ้นแต่มีประสิทธิภาพน้อยกว่าวิธีการเชื่อมต่อเพื่อนบ้าน การปรับปรุงเพิ่มเติมที่แก้ไขความสัมพันธ์ระหว่างระยะทางที่เกิดขึ้นจากลำดับที่มีความสัมพันธ์ใกล้ชิดกันจำนวนมากในชุดข้อมูลสามารถนำมาใช้ได้เช่นกัน แต่ต้องใช้ต้นทุนการคำนวณที่เพิ่มขึ้น^{[ 6 ]}

ฟังก์ชันทั่วไปในการทำเหมืองข้อมูลคือการใช้การวิเคราะห์คลัสเตอร์กับชุดข้อมูลที่กำหนด เพื่อจัดกลุ่มข้อมูลตามความคล้ายคลึงกัน หรือความคล้ายคลึงกันมากกว่าเมื่อเปรียบเทียบกับกลุ่มอื่นๆ เมทริกซ์ระยะทางกลายเป็นสิ่งสำคัญและถูกนำมาใช้ในการวิเคราะห์คลัสเตอร์ อย่างมาก เนื่องจากความคล้ายคลึงกันสามารถวัดได้ด้วยเมตริกซ์ระยะทาง ดังนั้น เมทริกซ์ระยะทางจึงกลายเป็นตัวแทนของการวัดความคล้ายคลึงกันระหว่างคู่ข้อมูลต่างๆ ในชุดข้อมูล

เมทริกซ์ระยะทางมีความจำเป็นสำหรับ อัลกอริธึมการจัด กลุ่มแบบลำดับชั้น แบบดั้งเดิม ซึ่งมักเป็นวิธีการเชิงฮิวริสติกที่ใช้ในวิทยาศาสตร์ชีวภาพ เช่น การสร้างแผนภูมิวิวัฒนาการ เมื่อนำอัลกอริธึมการจัดกลุ่มแบบลำดับชั้นใดๆ มาใช้ในการทำเหมืองข้อมูล เมทริกซ์ระยะทางจะประกอบด้วยระยะทางแบบคู่ระหว่างทุกจุด จากนั้นจะเริ่มสร้างกลุ่มระหว่างสองจุดที่แตกต่างกัน หรือกลุ่มโดยอาศัยระยะทางจากเมทริกซ์ระยะทางเท่านั้น

ถ้า N คือจำนวนจุด ความซับซ้อนของการจัดกลุ่มแบบลำดับชั้นคือ:

• ความซับซ้อนด้านเวลาเกิดจากการคำนวณซ้ำๆ ที่ทำหลังจากแต่ละคลัสเตอร์เพื่ออัปเดตเมทริกซ์ระยะทาง${\displaystyle O(N^{3})}$
• ความซับซ้อนของพื้นที่คือ${\displaystyle O(N^{2})}$

เมตริกระยะทางเป็นส่วนสำคัญของอัลกอริธึมการเรียนรู้ของเครื่องหลายอย่าง ซึ่งใช้ทั้งในการเรียนรู้แบบมีผู้กำกับดูแลและ แบบไม่มีผู้กำกับดูแล โดยทั่วไปจะใช้ในการคำนวณความคล้ายคลึงกันระหว่างจุดข้อมูล ซึ่งเมทริกซ์ระยะทางเป็นองค์ประกอบสำคัญ การใช้เมทริกซ์ระยะทางที่มีประสิทธิภาพช่วยปรับปรุงประสิทธิภาพของแบบจำลองการเรียนรู้ของเครื่อง ไม่ว่าจะเป็นสำหรับงานจำแนกประเภทหรือการจัดกลุ่ม^{[ 7 ]}

อัลกอริทึมk-NNเป็นหนึ่งในอัลกอริทึมการเรียนรู้ของเครื่องแบบอิงตัวอย่างที่ช้าที่สุด แต่เรียบง่ายที่สุดและใช้งานมากที่สุด ซึ่งสามารถใช้ได้ทั้งในงานจำแนกประเภทและการถดถอย อัลกอริทึมนี้ใช้เมทริกซ์ระยะทาง เนื่องจากผลลัพธ์ที่ทำนายได้ของแต่ละตัวอย่างทดสอบนั้นต้องใช้เมทริกซ์ระยะทางที่คำนวณอย่างสมบูรณ์ระหว่างตัวอย่างทดสอบและแต่ละตัวอย่างฝึกฝนในชุดฝึกฝน เมื่อคำนวณเมทริกซ์ระยะทางแล้ว อัลกอริทึมจะเลือกตัวอย่างฝึกฝนจำนวน K ตัวที่ใกล้เคียงกับตัวอย่างทดสอบมากที่สุด เพื่อทำนายผลลัพธ์ของตัวอย่างทดสอบโดยอิงจากค่าส่วนใหญ่ (การจำแนกประเภท) หรือค่าเฉลี่ย (การถดถอย) ของชุดที่เลือก

• ความซับซ้อนของเวลาในการทำนายคือเพื่อคำนวณระยะห่างระหว่างตัวอย่างทดสอบแต่ละตัวกับตัวอย่างฝึกฝนแต่ละตัว เพื่อสร้างเมทริกซ์ระยะห่าง โดยที่:${\displaystyle O(k*n*d)}$

1. k = จำนวนเพื่อนบ้านที่ใกล้ที่สุดที่ถูกเลือก
2. n = ขนาดของชุดข้อมูลฝึกฝน
3. d = จำนวนมิติที่ใช้สำหรับข้อมูล

โมเดลที่เน้นการจำแนกประเภทนี้จะทำนายป้ายกำกับของเป้าหมายโดยอาศัยเมทริกซ์ระยะห่างระหว่างเป้าหมายและตัวอย่างการฝึกอบรมแต่ละตัว เพื่อกำหนดจำนวนตัวอย่าง K ตัวที่ใกล้เคียงที่สุดกับเป้าหมาย

เมทริกซ์ระยะทางสามารถใช้ในโครงข่ายประสาทเทียมสำหรับการถดถอยจาก 2 มิติไปสู่ ​​3 มิติในแบบจำลองการเรียนรู้ของเครื่องสำหรับการทำนายภาพได้

• [1] * ระยะทางแบบผสมเกาส์เซียนสำหรับการค้นหาเพื่อนบ้านที่ใกล้ที่สุด อย่างแม่นยำ เพื่อการดึงข้อมูล ภายใต้แบบจำลองการผสมแบบจำกัดเกาส์เซียนที่กำหนดไว้สำหรับการกระจายของข้อมูลในฐานข้อมูล ระยะทางแบบผสมเกาส์เซียนได้รับการกำหนดสูตรโดยอิงจากการลดค่าความแตกต่าง Kullback–Leiblerระหว่างการกระจายของข้อมูลที่ดึงมาและข้อมูลในฐานข้อมูล ในการเปรียบเทียบประสิทธิภาพของระยะทางแบบผสมเกาส์เซียนกับ ระยะทางแบบ ยุคลิดและมาฮาลาโนบิส ที่เป็นที่รู้จักกันดี โดยอิงจากการวัดประสิทธิภาพความแม่นยำ ผลการทดลองแสดงให้เห็นว่าฟังก์ชันระยะทางแบบผสมเกาส์เซียนนั้นเหนือกว่าฟังก์ชันอื่นๆ สำหรับข้อมูลทดสอบประเภทต่างๆ

อัลกอริทึมพื้นฐานที่น่าสนใจในหัวข้อการค้นหาข้อมูลคือ อัลกอริทึมการค้นหา ฝูงปลา (Fish School Search algorithm) ซึ่งเป็นการค้นหาข้อมูลที่ใช้เมทริกซ์ระยะทางในการรวบรวมพฤติกรรมโดยรวมของฝูงปลา โดยใช้ตัวดำเนินการให้อาหารเพื่ออัปเดตน้ำหนักของพวกมัน

สมการ A:

${\displaystyle x_{i}(t+1)=x_{i}(t)-step_{vol}rand(0,1){\frac {x_{i}(t)-B(t)}{distance(x_{i}(t),B(t))}},}$

สมการ B:

${\displaystyle x_{i}(t+1)=x_{i}(t)+step_{vol}rand(0,1){\frac {x_{i}(t)-B(t)}{distance(x_{i}(t),B(t))}},}$

Stepvol กำหนดขนาดของการเคลื่อนย้ายปริมาตรสูงสุดที่เกิดขึ้นโดยใช้เมทริกซ์ระยะทาง โดยเฉพาะอย่างยิ่งการใช้เมทริกซ์ ระยะทางแบบยูคลิด

• [2]ในขณะที่ การวัด ความคล้ายคลึงแบบโคไซน์อาจเป็นการวัดความใกล้เคียงที่ใช้บ่อยที่สุดในการค้นหาข้อมูลโดยการวัดมุมระหว่างเอกสารในพื้นที่การค้นหาบนพื้นฐานของโคไซน์ ระยะทางแบบยูคลิดจะไม่เปลี่ยนแปลงเมื่อมีการแก้ไขค่าเฉลี่ย การแจกแจงตัวอย่างของค่าเฉลี่ยถูกสร้างขึ้นโดยการสุ่มตัวอย่างซ้ำๆ จากประชากรเดียวกันและบันทึกค่าเฉลี่ยของตัวอย่างที่ได้รับ ซึ่งก่อให้เกิดการแจกแจงของค่าเฉลี่ยที่แตกต่างกัน และการแจกแจงนี้มีค่าเฉลี่ยและความแปรปรวนของตัวเอง สำหรับข้อมูลที่อาจเป็นได้ทั้งค่าลบและค่าบวกการแจกแจงว่างสำหรับความคล้ายคลึงแบบโคไซน์คือการแจกแจงของผลคูณดอทของเวกเตอร์หน่วยสุ่มอิสระสองตัว การแจกแจงนี้มีค่าเฉลี่ยเป็นศูนย์และความแปรปรวนเป็น 1/n ในขณะที่ระยะทางแบบยูคลิดจะไม่เปลี่ยนแปลงเมื่อมีการแก้ไขนี้

การนำการจัดกลุ่มแบบลำดับชั้นโดยใช้เมตริกตามระยะทางมาใช้ในการจัดระเบียบและจัดกลุ่มเอกสารที่คล้ายคลึงกันเข้าด้วยกัน จะต้องใช้เมทริกซ์ระยะทาง เมทริกซ์ระยะทางนี้จะแสดงถึงระดับความสัมพันธ์ระหว่างเอกสารหนึ่งกับเอกสารอื่น ซึ่งจะนำมาใช้สร้างกลุ่มเอกสารที่มีความสัมพันธ์ใกล้ชิดกัน และนำไปใช้ในวิธีการค้นหาเอกสารที่เกี่ยวข้องกับคำค้นหาของผู้ใช้

Isomapผสานรวมเมทริกซ์ระยะทางเพื่อใช้ระยะทางเชิงภูมิศาสตร์ในการคำนวณการฝังข้อมูลในมิติที่ต่ำกว่า ซึ่งช่วยจัดการกับชุดเอกสารที่อยู่ในมิติจำนวนมหาศาล และช่วยให้สามารถจัดกลุ่มเอกสารได้

อัลกอริทึมที่ใช้สำหรับการแสดงภาพข้อมูลทั้งแบบไม่กำกับดูแลและแบบกำกับดูแล โดยใช้เมทริกซ์ระยะทางเพื่อค้นหาข้อมูลที่คล้ายคลึงกันโดยพิจารณาจากความคล้ายคลึงที่แสดงบนหน้าจอ/จอแสดงผล

เมทริกซ์ระยะทางที่จำเป็นสำหรับ NeRV แบบไม่ใช้การกำกับดูแล สามารถคำนวณได้โดยใช้ระยะทางแบบคู่คงที่ของข้อมูลป้อนเข้า

เมทริกซ์ระยะทางที่จำเป็นสำหรับ Supervised NeRV นั้น จำเป็นต้องสร้างเมตริกซ์ระยะทางแบบมีผู้กำกับดูแล เพื่อให้สามารถคำนวณระยะทางของข้อมูลนำเข้าในลักษณะที่มีการกำกับดูแลได้

เมทริกซ์ระยะทางเป็นวัตถุทางคณิตศาสตร์ที่ใช้กันอย่างแพร่หลายในเคมีทั้งในรูปแบบกราฟิกเชิงทฤษฎี (โทโพโลยี) และเรขาคณิต (โทโพกราฟิก) ^{[ 8 ]}เมทริกซ์ระยะทางถูกใช้ในเคมีทั้งในรูปแบบที่ชัดเจนและไม่ชัดเจน

เมทริกซ์ระยะทางถูกนำมาใช้เป็นวิธีการหลักในการแสดงและเปิดเผยลำดับเส้นทางที่สั้นที่สุดที่จำเป็นต่อการกำหนดการจัดเรียงใหม่ระหว่างไอโซเมอร์แบบสลับตำแหน่งทั้งสอง

จำเป็นต้องใช้เมทริกซ์ระยะทางอย่างชัดเจนในการสร้างพหุนามระยะทางและสเปกตรัมระยะทางของโครงสร้างโมเลกุล

มีการใช้เมทริกซ์ระยะทางโดยปริยายผ่านการใช้เมตริกซ์ระยะทางที่เรียกว่าเลขไวเนอร์ / ดัชนีไวเนอร์ซึ่งถูกกำหนดขึ้นเพื่อแสดงระยะทางในโครงสร้างทางเคมีทั้งหมด เลขไวเนอร์มีค่าเท่ากับครึ่งหนึ่งของผลรวมขององค์ประกอบในเมทริกซ์ระยะทาง

เมทริกซ์ระยะทางในวิชาเคมีใช้สำหรับการสร้างกราฟโมเลกุลแบบ 2 มิติ ซึ่งใช้เพื่อแสดงคุณลักษณะพื้นฐานหลักของโมเลกุลในแอปพลิเคชันต่างๆ มากมาย

1. การสร้างแผนผังแสดงโครงสร้างคาร์บอนของโมเลกุลโดยอิงจากเมทริกซ์ระยะทาง เมทริกซ์ระยะทางมีความสำคัญอย่างยิ่งในแอปพลิเคชันนี้ เนื่องจากโมเลกุลที่คล้ายกันอาจมีโครงสร้างคาร์บอนในรูปแบบแผนผังได้หลากหลายรูปแบบโครงสร้างแผนผังแสดงโครงสร้างคาร์บอนของเฮกเซน (C6H14 _{) ที่สร้างขึ้นโดยอิงจากเมทริกซ์ระยะทางในตัวอย่าง มีโครงสร้างคาร์บอนที่แตกต่างกันหลายแบบ ซึ่งส่งผลต่อทั้งเมทริก ซ์}ระยะทางและแผนผังแสดงโครงสร้าง
2. การสร้างกราฟที่มีป้ายกำกับและน้ำหนักของขอบ ซึ่งใช้ในทฤษฎีกราฟทางเคมีเพื่อแสดงโมเลกุลที่มีอะตอมต่างชนิดกัน
3. วิธี Le Verrier-Fadeev-Frame (LVFF) เป็นวิธีที่ใช้คอมพิวเตอร์เพื่อเร่งกระบวนการตรวจหาจุดศูนย์กลางของกราฟในกราฟแบบหลายวง อย่างไรก็ตาม LVFF ต้องการเมทริกซ์ระยะทางที่เป็นเมทริกซ์ทแยงมุมเป็นอินพุต ซึ่งสามารถแก้ไขได้ง่ายโดยการใช้ขั้นตอนวิธี Householder tridiagonal-QL ที่รับเมทริกซ์ระยะทางเป็นอินพุตและส่งคืนเมทริกซ์ระยะทางที่เป็นเมทริกซ์ทแยงมุมที่จำเป็นสำหรับวิธี LVFF

ในขณะที่เมทริกซ์ระยะทางเชิงกราฟ 2 มิติจับภาพคุณสมบัติโครงสร้างของโมเลกุล ลักษณะสามมิติ (3 มิติ) ของมันถูกเข้ารหัสในเมทริกซ์ระยะทางเชิงเรขาคณิต เมทริกซ์ระยะทางเชิงเรขาคณิตเป็นเมทริกซ์ระยะทางประเภทที่แตกต่างกันซึ่งอิงตามเมทริกซ์ระยะทางเชิงกราฟของโมเลกุลเพื่อแสดงและวาดกราฟโครงสร้างโมเลกุล 3 มิติ^{[ 8 ]}เมทริกซ์ระยะทางเชิงเรขาคณิตของโครงสร้างโมเลกุลGเป็นเมทริกซ์สมมาตรจริงn x nที่กำหนดในลักษณะเดียวกับเมทริกซ์ 2 มิติ อย่างไรก็ตาม องค์ประกอบเมทริกซ์D _ijจะเก็บชุดของระยะทางคาร์ทีเซียนที่สั้นที่สุดระหว่างiและjในGเมทริกซ์ระยะทางเชิงเรขาคณิต หรือที่รู้จักกันในชื่อเมทริกซ์ภูมิประเทศ สามารถสร้างขึ้นจากเรขาคณิตที่ทราบของโมเลกุล ตัวอย่างเช่น เมทริกซ์ระยะทางเชิงเรขาคณิตของโครงกระดูกคาร์บอนของ2,4-ไดเมทิลเฮกเซนแสดงไว้ด้านล่าง:

เมทริกซ์ระยะทาง Dynamic Time Warpingถูกนำมาใช้ร่วมกับอัลกอริธึมการจัดกลุ่มและการจำแนกประเภทของชุด/กลุ่มวัตถุอนุกรมเวลา

ตัวอย่างเช่น สมมติว่าข้อมูลเหล่านี้จะถูกนำมาวิเคราะห์ โดยที่ระยะทางแบบยูคลิดของพิกเซล เป็นตัววัดระยะทาง

เมทริกซ์ระยะทางจะเป็นดังนี้:

จากนั้นสามารถดูข้อมูลเหล่านี้ในรูปแบบกราฟิกเป็นแผนที่ความร้อนได้ในภาพนี้ สีดำแสดงถึงระยะทาง 0 และสีขาวแสดงถึงระยะทางสูงสุด

• คอมพิวเตอร์วิชั่น
• การจัดกลุ่มข้อมูล
• ตั้งระยะห่าง
• เมทริกซ์กลวง
• การคูณเมทริกซ์ Min-plus