กลับไปหน้าบทความ

อ่าน 2 นาที

กราฟลำดับ

กราฟเฉพาะแอปพลิเคชัน/ชีวสารสนเทศศาสตร์/ชีววิทยาเชิงวิวัฒนาการ/จีโนมิกส์

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

กราฟลำดับ

กราฟลำดับหรือเรียกอีกอย่างว่ากราฟการจัดเรียงกราฟจุดแตกหักหรือกราฟความสัมพันธ์เป็นกราฟแบบสองทิศทางที่ใช้ในจีโนมิกส์เชิงเปรียบเทียบโครงสร้างประกอบด้วยกราฟหรือจีโนม หลายกราฟ ที่มีขอบและจุดยอดหลายชุด ซึ่งแสดงถึงความสัมพันธ์ระหว่างส่วนต่างๆ ในจีโนม[ 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 ]

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Sequence_graph&oldid=1251742584 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ กราฟลำดับ

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

การก่อสร้าง

ก่อนที่จะสร้างกราฟลำดับ จะต้องมีจีโนมอย่างน้อยสองจีโนมที่แสดงเป็นกราฟทิศทางที่มีขอบเป็นเธรด (ขอบประชิด) และจุดยอดเป็นส่วนของ DNA จีโนมควรได้รับการติดป้ายกำกับ เป็น P และ Q ในขณะที่กราฟลำดับได้รับการติดป้ายกำกับเป็น BreakpointGraph( P, Q ) [ 2 ]

การสร้างจีโนมบรรพบุรุษขึ้นใหม่

Alekseyev และ Pevzner ใช้กราฟลำดับเพื่อสร้างอัลกอริทึมของตนเองเพื่อศึกษาประวัติการจัดเรียงจีโนมใหม่ของสัตว์เลี้ยงลูกด้วยนมหลายชนิด รวมถึงวิธีการเอาชนะปัญหาเกี่ยวกับการสร้างจีโนมบรรพบุรุษในปัจจุบัน [ 1 ]

การจัดเรียงลำดับหลายลำดับ

กราฟลำดับสามารถใช้เพื่อแสดง การจัดเรียงลำดับหลายลำดับ โดยการเพิ่มขอบชนิดใหม่ที่แสดงถึง ความเหมือนกัน ระหว่างส่วนต่างๆ [ 3 ] สำหรับชุดจีโนม เราสามารถสร้างกราฟจุดแตกหักแบบไม่มีวงจรโดยมีเธรดสำหรับแต่ละจีโนม สำหรับสองส่วนและโดยที่, , ,...