Velvetเป็นชุดอัลกอริทึมที่ได้รับการออกแบบมาเพื่อจัดการกับการประกอบจีโนมแบบ de novo และการจัดเรียงลำดับการ อ่านสั้น ซึ่งทำได้โดยการจัดการกราฟ de Bruijnสำหรับการประกอบลำดับจีโนมผ่านการกำจัดข้อผิดพลาดและการทำให้ภูมิภาคที่ซ้ำกันง่ายขึ้น^{[ 2 ]} Velvet ยังได้รับการนำไปใช้ในแพ็คเกจเชิงพาณิชย์ เช่นSequencher , Geneious , MacVectorและBioNumericsด้วย

การพัฒนาเครื่องจัดลำดับรุ่นต่อไป (NGS) ทำให้การจัดลำดับแบบอ่านสั้นมากมีประสิทธิภาพด้านต้นทุนมากขึ้น การจัดการกราฟ de Bruijn เป็นวิธีการจัดเรียงที่สมจริงมากขึ้น แต่ยังจำเป็นต้องมีการพัฒนาเพิ่มเติมเพื่อแก้ไขปัญหาเกี่ยวกับข้อผิดพลาดและการทำซ้ำ^{[ 3 ]}ซึ่งนำไปสู่การพัฒนา Velvet โดย Daniel Zerbino และEwan Birneyที่สถาบันชีวสารสนเทศแห่งยุโรปในสหราชอาณาจักร^{[ 4 ]}

Velvet ทำงานโดยการจัดการกราฟ de Bruijn อย่างมีประสิทธิภาพผ่านการลดรูปและการบีบอัด โดยไม่สูญเสียข้อมูลของกราฟ ด้วยการรวมเส้นทางที่ไม่ตัดกันเข้าเป็นโหนดเดียว มันกำจัดข้อผิดพลาดและแก้ไขปัญหาการซ้ำซ้อนโดยเริ่มจากการใช้อัลกอริธึมแก้ไขข้อผิดพลาดที่รวมลำดับเข้าด้วยกัน จากนั้นจึงลบส่วนที่ซ้ำซ้อนออกจากลำดับโดยใช้ตัวแก้ปัญหาการซ้ำซ้อนที่แยกเส้นทางที่มีการทับซ้อนกันในระดับท้องถิ่น

การผสมผสานระหว่างลำดับอ่านสั้นและลำดับอ่านคู่ช่วยให้ Velvet สามารถแยกแยะลำดับซ้ำขนาดเล็กและสร้างคอนติ๊กที่มีความยาวเหมาะสมได้ การประยุกต์ใช้ Velvet ในลักษณะนี้สามารถสร้างคอนติ๊กที่มี ความยาว N50 50 กิโลเบสสำหรับข้อมูล โปรคาริโอตแบบคู่ปลายและความยาว 3 กิโลเบสสำหรับบริเวณข้อมูล ของสัตว์ เลี้ยงลูกด้วยนม

ดังที่ได้กล่าวไปแล้ว Velvet ใช้กราฟ de Bruijn ในการประกอบลำดับดีเอ็นเอสั้นๆ โดยเฉพาะอย่างยิ่ง Velvet จะแสดงk-mer ที่แตกต่างกันแต่ละตัว ที่ได้จากลำดับดีเอ็นเอด้วยโหนดที่ไม่ซ้ำกันบนกราฟ โหนดสองโหนดจะเชื่อมต่อกันหาก k-mer ของทั้งสองโหนดมีส่วนที่ทับซ้อนกัน k-1 กล่าวอีกนัยหนึ่งคือ ส่วนโค้งจากโหนด A ไปยังโหนด B จะมีอยู่หากอักขระ k-1 ตัวสุดท้ายของ k-mer ที่แสดงโดย A เป็นอักขระ k-1 ตัวแรกของ k-mer ที่แสดงโดย B ภาพต่อไปนี้แสดงตัวอย่างของกราฟ de Bruijn ที่สร้างด้วย Velvet:

กระบวนการเดียวกันนี้จะดำเนินการพร้อมกันกับส่วนเติมเต็มผกผันของ k-mer ทั้งหมด เพื่อพิจารณาถึงส่วนที่ทับซ้อนกันระหว่างการอ่านของสายตรงข้าม สามารถทำการปรับปรุงประสิทธิภาพหลายอย่างกับกราฟได้ ซึ่งรวมถึงการทำให้ง่ายขึ้นและการกำจัดข้อผิดพลาด

การทำให้ง่ายขึ้น

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

การแก้ไขข้อผิดพลาด

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

เคล็ดลับ

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

ฟองอากาศ

ฟองอากาศเกิดขึ้นเมื่อเส้นทางสองเส้นที่แตกต่างกันเริ่มต้นและสิ้นสุดที่โหนดเดียวกัน โดยปกติฟองอากาศเกิดจากข้อผิดพลาดหรือความแปรปรวนทางชีวภาพ ข้อผิดพลาดเหล่านี้จะถูกกำจัดโดยใช้อัลกอริทึม Tour Bus ซึ่งคล้ายกับอัลกอริทึมของ Dijkstra ซึ่งเป็นการค้นหาแบบกว้าง ( breadth -first search ) ที่ตรวจจับเส้นทางที่ดีที่สุดที่จะปฏิบัติตามและพิจารณาว่าควรลบเส้นทางใดออก ตัวอย่างง่ายๆ แสดงในรูปที่ 4

กระบวนการนี้ยังแสดงไว้ในรูปที่ 5 โดยต่อเนื่องจากตัวอย่างที่แสดงในรูปที่ 1 และ 2

การเชื่อมต่อที่ผิดพลาด

นี่คือการเชื่อมต่อที่ไม่สร้างเส้นทางที่ถูกต้อง หรือไม่สร้างโครงสร้างที่สามารถระบุได้ภายในกราฟ Velvet จะลบข้อผิดพลาดเหล่านี้หลังจากเสร็จสิ้นอัลกอริทึม Tour Bus โดยใช้การตัดขอบความครอบคลุมอย่างง่ายที่ผู้ใช้ต้องกำหนด

Velvet มีฟังก์ชันดังต่อไปนี้:

กำมะหยี่

คำสั่งนี้ช่วยสร้างชุดข้อมูล (สร้างแฮชให้กับลำดับการอ่าน) สำหรับvelvetgและรวมถึงข้อมูลเกี่ยวกับความหมายของไฟล์ลำดับแต่ละไฟล์ด้วย

กำมะหยี่

คำสั่งนี้จะสร้างกราฟ de Bruijn จาก k-mer ที่ได้จากvelvethและทำการลดความซับซ้อนและการแก้ไขข้อผิดพลาดบนกราฟ จากนั้นจึงแยกคอนทิกออกมา

หลังจากรันvelvetgแล้วจะมีการสร้างไฟล์จำนวนหนึ่ง ไฟล์ที่สำคัญที่สุดคือไฟล์ contigs ซึ่งประกอบด้วยลำดับของ contigs ที่มีความยาวมากกว่า 2k โดยที่ k คือความยาวของคำที่ใช้ในvelveth

สำหรับรายละเอียดและตัวอย่างเพิ่มเติม โปรดดูคู่มือ Velvet ^{[ 5 ]}

เทคโนโลยีการจัดลำดับดีเอ็นเอในปัจจุบัน รวมถึง NGS มีข้อจำกัดเนื่องจากจีโนมมีขนาดใหญ่กว่าความยาวของการอ่านมาก โดยทั่วไป NGS ทำงานกับการอ่านขนาดเล็ก น้อยกว่า 400 bp และมีต้นทุนต่อการอ่านต่ำกว่าเครื่องรุ่นแรก มาก นอกจากนี้ยังใช้งานง่ายกว่า มีการทำงานแบบขนานที่สูงกว่า และให้ผลผลิตสูงกว่า^{[ 3 ]}

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

เพื่อแก้ไขปัญหาเหล่านี้ จึงได้มีการพัฒนาโปรแกรมจัดลำดับแบบไดนามิกที่มีประสิทธิภาพ คุ้มค่า และสามารถแก้ไขข้อผิดพลาดและการทำซ้ำได้ อัลกอริทึม Velvet ได้รับการออกแบบมาเพื่อสิ่งนี้ และสามารถจัดเรียงลำดับการอ่านสั้นแบบ de novo ได้ในเวลาการคำนวณที่ค่อนข้างสั้นและใช้หน่วยความจำน้อยกว่าเมื่อเทียบกับโปรแกรมประกอบอื่นๆ^{[ 6 ]}

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

• โปรแกรมประกอบลำดับดีเอ็นเอแบบ de novo
• SPAdes (ซอฟต์แวร์)