Clustalเป็นโปรแกรมคอมพิวเตอร์ที่ใช้สำหรับการจัดเรียงลำดับหลายลำดับในชีวสารสนเทศ [ ^{2 ] เป็น}หนึ่งในซอฟต์แวร์ชีวสารสนเทศที่มีการอ้างอิงมากที่สุด โดยมีผลงานตีพิมพ์ทางวิชาการสองฉบับอยู่ใน 100 บทความที่มีการอ้างอิงมากที่สุดตลอดกาล ตามรายงานของNatureในปี 2014 ^{[ 3 ]}

นับตั้งแต่ตีพิมพ์ครั้งแรกในปี 1988 ซอฟต์แวร์และอัลกอริทึมของมันได้รับการพัฒนามาหลายรุ่น โดย ClustalΩ (Omega) เป็นเวอร์ชันล่าสุด ณ ปี 2011 สามารถใช้งานได้ทั้งในรูปแบบซอฟต์แวร์แบบติดตั้งบนเครื่อง ผ่านทางเว็บอินเทอร์เฟซและผ่านทางเซิร์ฟเวอร์ที่ดูแลโดยสถาบันชีวสารสนเทศแห่งยุโรป (European Bioinformatics Institute )

แผนผังต้นไม้ในเวอร์ชันเริ่มต้นของ Clustal ถูกสร้างขึ้นผ่าน การวิเคราะห์คลัสเตอร์ UPGMAของการจัดเรียงแบบคู่ ดังนั้นจึงได้ชื่อว่า CLUSTAL ^{[ 4 ]ดู[ 5 ]}เวอร์ชันสี่เวอร์ชันแรกของ Clustal ใช้เลขอารบิก (1 ถึง 4) ในขณะที่เวอร์ชันที่ห้าใช้เลขโรมัน V ^{[ 4 ]ดู[ 6 ] [ 7 ]}เวอร์ชันสองเวอร์ชันถัดไปใช้ตัวอักษรละติน โดย W หมายถึง weighted และ X หมายถึงX Windowเพื่อแสดงถึงการเปลี่ยนแปลงที่เกิดขึ้น^{[ 4 ]ดู[ 8 ] [ 9 ]}ชื่อ Omega ถูกเลือกเพื่อแสดงถึงการเปลี่ยนแปลงจากเวอร์ชันก่อนหน้า^{[ 4 ]}

• Clustal : ซอฟต์แวร์ดั้งเดิมสำหรับการจัดเรียงลำดับหลายลำดับ สร้างโดยDes Higginsในปี 1988 โดยอาศัยการสร้างแผนผังนำทางจากลำดับคู่ของกรดอะมิโนหรือ นิว คลีโอไทด์^{[ 10 ]}
• ClustalV : Clustal รุ่นที่สอง เปิดตัวในปี 1992 โดยนำเสนอความสามารถในการสร้างการจัดเรียงลำดับใหม่จากการจัดเรียงลำดับที่มีอยู่แล้วในกระบวนการที่เรียกว่าการสร้างแผนภูมิวิวัฒนาการ ClustalV ยังเพิ่มตัวเลือกในการสร้างแผนภูมิโดยใช้วิธีการเชื่อมต่อเพื่อนบ้าน^{[ 7 ]}
• ClustalW : รุ่นที่สาม เปิดตัวในปี 1994 โดยปรับปรุงอัลกอริทึมการจัดเรียงแบบก้าวหน้า รวมถึง ตัวเลือก การถ่วงน้ำหนัก ลำดับ ตามความคล้ายคลึงและความแตกต่างนอกจากนี้ยังเพิ่มตัวเลือกในการเรียกใช้ Clustal ในโหมดแบตช์จาก บรรทัด คำสั่ง^{[ 11 ]}
• ClustalX : เปิดตัวในปี 1997 ซึ่งเป็นเวอร์ชันแรกที่มีอินเทอร์เฟซผู้ใช้แบบกราฟิก^{[ 9 ]}
• Clustal2 : เวอร์ชันนี้ได้รับการปรับปรุงจากทั้ง ClustalW และ ClustalX ให้มีความแม่นยำและประสิทธิภาพที่สูงขึ้นในปี 2550 ^{[ 12 ]}
• ClustalΩ (โอเมก้า) : เวอร์ชันปัจจุบัน เปิดตัวในปี 2011 ^{[ 13 ] [ 14 ]}

Clustal จัดเรียงลำดับโดยใช้ฮิวริสติกที่ สร้างการจัดเรียงลำดับหลาย ลำดับจากชุดการจัดเรียงแบบคู่ทีละคู่ วิธีนี้ทำงานโดยการวิเคราะห์ลำดับทั้งหมดและใช้วิธี UPGMA/neighbor-joining เพื่อสร้างเมทริกซ์ระยะทางต้นไม้แนะนำจะถูกคำนวณจากคะแนนของลำดับในเมทริกซ์ จากนั้นจึงใช้เพื่อสร้างการจัดเรียงลำดับหลายลำดับโดยการจัดเรียงลำดับตามลำดับความคล้ายคลึงกันทีละน้อย^{[ 15 ]}

Clustal สร้างการจัดเรียงลำดับหลายลำดับผ่านสามขั้นตอนหลัก:

1. ทำการจัดเรียงลำดับแบบคู่โดยใช้วิธีการจัดเรียงลำดับแบบก้าวหน้า
2. สร้างแผนผังแนะนำ (หรือใช้แผนผังที่ผู้ใช้กำหนดเอง)
3. ใช้แผนผังต้นไม้เป็นแนวทางในการจัดเรียงลำดับหลายรายการ

ขั้นตอนเหล่านี้จะดำเนินการโดยอัตโนมัติด้วยฟังก์ชัน "ทำการจัดเรียงลำดับทั้งหมด" ตัวเลือกอื่นๆ ได้แก่ "ทำการจัดเรียงลำดับจากแผนภูมินำทางและแผนภูมิวิวัฒนาการ" และ "สร้างแผนภูมินำทางเท่านั้น"

โปรแกรมนี้รองรับรูปแบบข้อมูลนำเข้าที่หลากหลาย รวมถึง NBRF/ PIR , FASTA , EMBL/ Swiss-Prot , Clustal, GCC/MSF, GCG9 RSF และ GDE

รูปแบบผลลัพธ์สามารถเป็นรูปแบบใดรูปแบบหนึ่งหรือหลายรูปแบบต่อไปนี้: Clustal, NBRF/ PIR , GCG /MSF, PHYLIP , GDE หรือ NEXUS

สัญลักษณ์ที่แสดงนั้นเหมือนกันทั้งสำหรับ การจัดเรียงลำดับ DNA / RNAและ การจัดเรียงลำดับ โปรตีนดังนั้นในขณะที่สัญลักษณ์ * (ดอกจัน) มีประโยชน์สำหรับทั้งสองกรณี สัญลักษณ์ฉันทามติอื่นๆ ควรถูกละเลยสำหรับการจัดเรียงลำดับ DNA/RNA

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

ซอฟต์แวร์ Clustal ดั้งเดิมได้รับการพัฒนาขึ้นในปี 1988 ในฐานะวิธีการคำนวณสำหรับการสร้างการจัดเรียงลำดับหลายลำดับบนคอมพิวเตอร์ส่วนบุคคล ClustalV ซึ่งเปิดตัวในอีก 4 ปีต่อมา เป็นการเขียนใหม่ทั้งหมด โดยใช้ภาษา Cแทนภาษา Fortran

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

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

clustalv nameoffile . seq

หรือ

clustalv / infile = nameoffile . seq

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

ClustalW ใช้ระเบียบวิธีจัดเรียงลำดับแบบก้าวหน้า ซึ่งจะจัดลำดับความสำคัญของลำดับเพื่อจัดเรียงตามความคล้ายคลึงกันจนกว่าจะได้การจัดเรียงโดยรวม นอกจากนี้ยังเป็น อัลกอริทึม แบบเมทริกซ์ในขณะที่เครื่องมืออย่างT-CoffeeและDialignใช้หลักการความสอดคล้อง โปรแกรมนี้ต้องการลำดับอย่างน้อยสามลำดับขึ้นไปเพื่อคำนวณการจัดเรียงโดยรวม สำหรับการจัดเรียงลำดับแบบไบนารี ควรใช้ เครื่องมืออื่น เช่นEMBOSS หรือ LALIGN

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

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

ClustalW มีความซับซ้อนเชิงเวลาเนื่องจากใช้เมธอด neighbor-joining ${\displaystyle O(N^{2})}$

ClustalW2 เพิ่มตัวเลือกให้ใช้ UPGMA แทน ซึ่งเร็วกว่าสำหรับข้อมูลขนาดใหญ่ คำสั่งบรรทัดคำสั่งที่จะใช้แทนวิธี Neighbor-Joining คือ:

- การจัดกลุ่ม= UPGMA

ยกตัวอย่างเช่น หากใช้เทคนิค Neighbor-Joining กับข้อมูลลำดับ 10,000 ชุด จะใช้เวลามากกว่าหนึ่งชั่วโมง แต่เทคนิค UPGMA จะเสร็จสิ้นภายในเวลาไม่ถึงหนึ่งนาที

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

ตัวเลือกต่อไปนี้จะเปิดใช้งานการจัดเรียงแบบวนซ้ำ:

- การวนซ้ำ= การจัดแนว- การวนซ้ำ= ต้นไม้- จำนวน

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

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

เมื่อมีการเปรียบเทียบอัลกอริทึมการจัดเรียงลำดับหลายลำดับในปี 2014 ClustalW เป็นหนึ่งในอัลกอริทึมที่เร็วที่สุดที่สามารถสร้างผลลัพธ์ได้ในระดับความแม่นยำที่ต้องการ อย่างไรก็ตาม มันไม่แม่นยำเท่ากับคู่แข่งที่ใช้ความสอดคล้อง เช่น T-Coffee ^{[ 19 ]}ในบรรดา MAFFT, T-Coffee และ Clustal Omega นั้น ClustalW มีความแม่นยำต่ำที่สุดสำหรับลำดับความยาวเต็ม แต่ความแม่นยำของมันยังคงถือว่ายอมรับได้ นอกจากนี้ ClustalW ยังเป็นอัลกอริทึมที่มีประสิทธิภาพด้านหน่วยความจำมากที่สุดในบรรดาอัลกอริทึมที่ศึกษา^{[ 19 ]}การอัปเดตซอฟต์แวร์อย่างต่อเนื่องทำให้ ClustalW2 มีความแม่นยำมากขึ้นในขณะที่ยังคงรักษาความเร็วนี้ไว้^{[ 18 ]}

ClustalΩ (หรือเขียนอีกแบบว่า Clustal O และ Clustal Omega) เขียนด้วยภาษา C และC++โดยใช้ไกด์ทรีแบบมีเมล็ดและ เอนจิน HMM ใหม่ ที่เน้นโปรไฟล์สองโปรไฟล์เพื่อสร้างการจัดเรียงเหล่านี้^{[ 20 ] [ 21 ]}โปรแกรมต้องการลำดับอย่างน้อยสามลำดับขึ้นไปเพื่อคำนวณการจัดเรียงลำดับหลายลำดับ Clustal Omega ใช้หลักการความสอดคล้องและได้รับการยกย่องอย่างกว้างขวางว่าเป็นหนึ่งในเครื่องมือจัดเรียงลำดับหลายลำดับที่เร็วที่สุดแบบออนไลน์ และยังคงมีความแม่นยำสูงทั้งในกลุ่มอัลกอริธึมแบบใช้หลักการความสอดคล้องและแบบใช้เมทริกซ์

Clustal Omega มีขั้นตอนหลักห้าขั้นตอนในการสร้าง การ จัด เรียงลำดับหลายลำดับ

1. การจัดเรียงแบบคู่จะถูกสร้างขึ้นโดยใช้วิธี k-tuple ซึ่งเป็นวิธีการเชิงฮิวริสติกที่ไม่รับประกันว่าจะได้คำตอบที่ดีที่สุด แต่มีประสิทธิภาพมากกว่าการใช้ การเขียนโปรแกรม แบบไดนามิก
2. ลำดับจะถูกจัดกลุ่มโดยใช้วิธี mBed ที่แก้ไขแล้ว^{[ 22 ]}วิธี mBed คำนวณระยะทางแบบคู่โดยใช้การฝังลำดับ
3. ใช้วิธี การจัดกลุ่มแบบ k -means
4. มีการสร้างแผนผังนำทางโดยใช้วิธี UPGMAในภาพด้านขวา แสดงให้เห็นถึงขั้นตอนการสร้างแผนผังนำทางหลายขั้นตอนซึ่งนำไปสู่การสร้างแผนผังนำทางขั้นสุดท้ายเพียงแผนผังเดียว เนื่องจากลักษณะการรวมกลุ่มของ UPGMA ในแต่ละขั้นตอน (รูปเพชรในแผนผัง) กลุ่มคลัสเตอร์ที่อยู่ใกล้กันที่สุดสองกลุ่มจะถูกรวมเข้าด้วยกัน กระบวนการนี้จะทำซ้ำจนกว่าจะสามารถประเมินแผนผังโดยรวมขั้นสุดท้ายได้
5. การจัดเรียงลำดับหลายลำดับขั้นสุดท้ายจะถูกสร้างขึ้นด้วยแพ็คเกจ HHAlign จากHH-Suite โดยใช้ HMMโปรไฟล์สองตัวHMM โปรไฟล์เป็นเครื่องสถานะเชิงเส้นที่ประกอบด้วยชุดของโหนด ซึ่งแต่ละโหนดจะสอดคล้องกับตำแหน่ง (คอลัมน์) ในการจัดเรียงที่สร้างขึ้นโดยประมาณ^{[ 23 ]}

ความซับซ้อนของเวลาในการคำนวณการจัดเรียงลำดับที่เหมาะสมที่สุดของลำดับที่มีความยาวนั้นสูงมาก จนเกินไป แม้แต่กับลำดับจำนวนน้อยก็ตาม เพื่อจัดการกับปัญหานี้ Clustal Omega จึงใช้ mBed เวอร์ชันที่ปรับปรุงแล้ว ซึ่งมีความซับซ้อนอยู่ที่[ ^{22 ] [ 24 ] และ}สร้างต้นไม้นำทางที่มีความแม่นยำเท่ากับวิธีการทั่วไป ความเร็วและความแม่นยำของต้นไม้นำทางใน Clustal Omega เกิดจากการนำอัลกอริทึม mBed ที่ปรับปรุงแล้วมาใช้ นอกจากนี้ยังช่วยลดเวลาในการคำนวณและความต้องการหน่วยความจำในการจัดเรียงลำดับบนชุดข้อมูลขนาดใหญ่อีกด้วย ${\displaystyle N}$${\displaystyle L}$${\displaystyle O(L^{N})}$${\displaystyle O(N\log N)}$

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

Clustal Omega ใช้แพ็คเกจ HHAlign ของ HH-Suite ซึ่งจัดเรียง Hidden Markov Model สองโปรไฟล์แทนที่จะเปรียบเทียบโปรไฟล์ต่อโปรไฟล์ วิธีนี้ช่วยปรับปรุงคุณภาพของความไวและการจัดเรียงอย่างมีนัยสำคัญ^{[ 25 ]}เมื่อรวมกับวิธี mBed แล้ว Clustal Omega จึงมีข้อได้เปรียบเหนือโปรแกรมจัดเรียงลำดับอื่นๆ

ในชุดข้อมูลที่มีฐานเทอร์มินัลที่ไม่ได้รับการอนุรักษ์ Clustal Omega อาจมีความแม่นยำมากกว่าProbconsหรือT-Coffeeแม้ว่าทั้งสองจะเป็นอัลกอริธึมที่อิงตามความสอดคล้องก็ตาม ในการทดสอบประสิทธิภาพด้วยโปรแกรมที่ให้คะแนนความแม่นยำสูงMAFFTเร็วที่สุด ตามมาด้วย Clustal Omega อย่างใกล้ชิด ทั้งสองเร็วกว่า T-Coffee อย่างไรก็ตามMAFFTและ Clustal Omega ต้องการหน่วยความจำในการทำงานมากกว่า^{[ 19 ]}

Clustal2คือเวอร์ชันที่รวมเอาทั้ง ClustalW เวอร์ชันใช้งานผ่านบรรทัดคำสั่ง และ Clustal X เวอร์ชันกราฟิกเข้าไว้ด้วยกัน ทั้งสองโปรแกรมไม่ใช่เครื่องมือใหม่ แต่เป็นเวอร์ชันที่ได้รับการปรับปรุงและพัฒนาจากเวอร์ชันก่อนหน้า ไฟล์ดาวน์โหลดทั้งสองเวอร์ชันได้รับการคอมไพล์ไว้ล่วงหน้าสำหรับระบบปฏิบัติการหลายระบบ เช่น Linux, Mac OS X และ Windows (ทั้ง XP และ Vista) การเปิดตัวครั้งนี้มีจุดประสงค์เพื่อให้เว็บไซต์มีความเป็นระเบียบและใช้งานง่ายยิ่งขึ้น รวมถึงการอัปเดตซอร์สโค้ดให้เป็นเวอร์ชันล่าสุด Clustal2 คือเวอร์ชัน 2 ของทั้ง ClustalW และ ClustalX ซึ่งเป็นที่มาของชื่อ เวอร์ชันก่อนหน้ายังคงสามารถพบได้บนเว็บไซต์ แต่ไฟล์ที่คอมไพล์ไว้ล่วงหน้าทั้งหมดได้รับการอัปเดตเป็นเวอร์ชันล่าสุดแล้ว

• หน้าแรกของ Clustal (ดาวน์โหลดฟรีสำหรับ Unix/Linux, Mac และ Windows)
• Clustal Omega mirror ที่ EBI