กราฟลำดับ
กราฟลำดับหรือเรียกอีกอย่างว่ากราฟการจัดเรียงกราฟจุดแตกหักหรือกราฟความสัมพันธ์เป็นกราฟแบบสองทิศทางที่ใช้ในจีโนมิกส์เชิงเปรียบเทียบโครงสร้างประกอบด้วยกราฟหรือจีโนม หลายกราฟ ที่มีขอบและจุดยอดหลายชุด ซึ่งแสดงถึงความสัมพันธ์ระหว่างส่วนต่างๆ ในจีโนม[ 1 ]และ ส่วนของ DNAตามลำดับ การสำรวจส่วนประกอบที่เชื่อมต่อกันของส่วนต่างๆ และขอบความสัมพันธ์ (เรียกว่าเธรด ) จะได้ลำดับ ซึ่งโดยทั่วไปจะแสดงถึงจีโนมหรือส่วนหนึ่งของจีโนม ส่วนต่างๆ สามารถคิดได้ว่าเป็น บล็อก ซินเทนีโดยขอบจะกำหนดวิธีการจัดเรียงบล็อกเหล่านี้ในจีโนมเฉพาะ และการติดป้ายกำกับขอบความสัมพันธ์จะแสดงถึงเบสที่ไม่ได้อยู่ในบล็อกซินเทนี
การก่อสร้าง
ก่อนที่จะสร้างกราฟลำดับ จะต้องมีจีโนมอย่างน้อยสองจีโนมที่แสดงเป็นกราฟทิศทางที่มีขอบเป็นเธรด (ขอบประชิด) และจุดยอดเป็นส่วนของ DNA จีโนมควรได้รับการติดป้ายกำกับ เป็น PและQในขณะที่กราฟลำดับได้รับการติดป้ายกำกับเป็น BreakpointGraph( P, Q ) [ 2 ]
จุดยอดทิศทางของ Q และขอบของจุดยอดเหล่านั้นจะถูกจัดเรียงตามลำดับของ P เมื่อเสร็จสมบูรณ์แล้ว ขอบของ Q จะถูกเชื่อมต่อกลับไปยังจุดยอดเดิม หลังจากที่ขอบทั้งหมดถูกจับคู่แล้ว ทิศทางของจุดยอดจะถูกลบออก และแทนที่ด้วยป้ายกำกับ v h (หัวจุดยอด) และ v t (หางจุดยอด)
ความคล้ายคลึงกันระหว่างจีโนมแสดงโดยจำนวนวงจร (ระบบอิสระ) ภายในกราฟลำดับ จำนวนวงจรเท่ากับจำนวนวงจร (P, Q) จำนวนวงจรสูงสุดที่เป็นไปได้เท่ากับจำนวนจุดยอดในกราฟลำดับ
ตัวอย่าง
ตัวอย่างรูปภาพ
เมื่อได้รับจีโนม P (+a +b -c) และ Q (+a +b -c) [ 1 ]ควรจัดเรียง Q ใหม่ให้เป็นไปตามทิศทางของขอบ (สีแดง) ของ P จุดยอดควรเปลี่ยนชื่อจาก a, b, c เป็น a h a t , b h b t , c h c tและขอบของ P และ Q ควรเชื่อมต่อกับจุดยอดเดิม (ขอบของ P = สีดำ ขอบของ Q = สีเขียว) ลบขอบที่มีทิศทาง (สีแดง) จำนวนรอบใน G(P, Q) คือ 1 ในขณะที่ค่าสูงสุดที่เป็นไปได้คือ 3
แอปพลิเคชัน
การสร้างจีโนมบรรพบุรุษขึ้นใหม่
Alekseyev และ Pevzner ใช้กราฟลำดับเพื่อสร้างอัลกอริทึมของตนเองเพื่อศึกษาประวัติการจัดเรียงจีโนมใหม่ของสัตว์เลี้ยงลูกด้วยนมหลายชนิด รวมถึงวิธีการเอาชนะปัญหาเกี่ยวกับการสร้างจีโนมบรรพบุรุษในปัจจุบัน[ 1 ]
การจัดเรียงลำดับหลายลำดับ
กราฟลำดับสามารถใช้เพื่อแสดงการจัดเรียงลำดับหลายลำดับโดยการเพิ่มขอบชนิดใหม่ที่แสดงถึงความเหมือนกันระหว่างส่วนต่างๆ[ 3 ]สำหรับชุดจีโนม เราสามารถสร้างกราฟจุดแตกหักแบบไม่มีวงจรโดยมีเธรดสำหรับแต่ละจีโนม สำหรับสองส่วนและโดยที่, , , และแทนจุดสิ้นสุดของสองส่วนนั้น สามารถสร้างขอบความเหมือนกันจากไปยังและไปยังหรือจากไปยังและไปยังซึ่งแสดงถึงทิศทางที่เป็นไปได้สองทิศทางของความเหมือนกัน ข้อดีของการแสดงการจัดเรียงลำดับหลายลำดับด้วยวิธีนี้คือสามารถรวมการผกผันและการจัดเรียงโครงสร้างอื่นๆ ที่ไม่สามารถทำได้ในการแสดงแบบเมทริกซ์
แสดงถึงความแปรผัน
หากมีเส้นทางที่เป็นไปได้หลายเส้นทางเมื่อเดินทางผ่านเธรดในกราฟลำดับ ลำดับหลายลำดับสามารถแสดงได้ด้วยเธรดเดียวกัน ซึ่งหมายความว่าสามารถสร้างกราฟลำดับที่แสดงถึงประชากรของบุคคลที่มีจีโนมแตกต่างกันเล็กน้อย โดยแต่ละจีโนมจะสอดคล้องกับเส้นทางหนึ่งผ่านกราฟ กราฟเหล่านี้ได้รับการเสนอให้ใช้แทน จีโน มมนุษย์อ้างอิง[ 4 ]