Multiple duplicated gene rearrangement algorithm for arbitrary target

ขั้นตอนวิธีการจัดเรียงหน่วยพันธุกรรมที่ซ้ำซ้อนหลายครั้งไปยังเป้าหมายใดๆ

Name: Jakkarin Suksawatchon

LCSH: Heredity

LCSH: Genomes

LCSH: Mutation (Biology)

LCSH: Multi-gene families

LCSH: Genome rearrangement

LCSH: Gene duplication

Abstract: The genome rearrangement can be used as a measurement of evolutionary distance between two organisms using the gene order of genomic data. The ultimate goal of genome rearrangement studies is finding a series of rearrangement scenarios to transform one genome into another by using the minimum number of the rearrangement events such as reversal, transposition and transversal. Hannenhalli and Pevzner introduced the notion of breakpoint graph to compute the reversal distance. Their algorithm determines the minimum number of reversals required for rearranging a genome to another -- but only in the absence of gene duplicates. However, duplicates often account for 40% of a genome. Therefore, the idea of breakpoint graph is clearly unsuitable for computing the reversal distances for multi-gene families. In this dissertation, we show how to extend Hannenhalli and Pevzner's approach to deal with genomes with multi-gene families. We propose a new heuristic algorithm to compute the reversal distances between two genomes with multi-gene families via binary integer programming. Then, we will be applied for the others two rearrangement distance (transposition and transversal). The experimental results on both synthetic and real biological data demonstrate that the proposed algorithm is able to find the reversal distance with high accuracy.

Abstract: การจัดเรียงหน่วยพันธุกรรมสามารถนำมาใช้เป็นเครื่องมือวัดระยะห่างทางวิวัฒนาการระหว่างสองสิ่งมีชีวิตใดๆ โดยใช้ลำดับของยีนในสายพันธุกรรม ซึ่งจุดมุ่งหมายหลักในการศึกษาการจัดเรียงหน่วยพันธุกรรมนั้นเป็นการหาลำดับในการจัดเรียงหน่วยพันธุกรรมจากจีโนมหนึ่งไปอีกจีโนมหนึ่ง โดยใช้จำนวนที่น้อยที่สุดของเหตุการณ์ที่ใช้ในการจัดเรียงหน่วยพันธุกรรม เช่น การกลายพันธุ์แบบหมุนวน (reversal), การกลายพันธุ์แบบแทรก (transposition) และการกลายพันธุ์แบบการหมุนวนและแทรก (transversal) Hannenhalli และ Pevzner ได้นำเสนอแนวคิดของกราฟที่มีจุดเปลี่ยน (breakpoint graph) มาใช้ในการคำนวณหาระยะห่างทางวิวัฒนาการของการกลายพันธุ์แบบหมุนวน ซึ่งขั้นตอนวิธีของ Hannenhalli และ Pevzner เป็นการหาจำนวนที่ใช้ในการเรียงลำดับเหตุการณ์ที่น้อยที่สุด ที่ใช้ในการจัดเรียงหน่วยพันธุกรรมจากจีโนมหนึ่งไปยังจีโนมหนึ่งของสายพันธุกรรมที่มีการกลายพันธุ์ ซึ่งขึ้นตอนวิธีดังกล่าวเหมาะสำหรับสายพันธุกรรมที่ไม่มีการซ้ำซ้อนกันของยีน แต่ในความเป็นจริงพบว่าในสายพันธุกรรมหนึ่งจะมีการซ้ำซ้อนกันของยีนอยู่ประมาณ 40 เปอร์เซ็นต์ จึงทำให้แนวคิดของกราฟที่มีจุดเปลี่ยนไม่เหมาะสมที่จะนำมาประยุกต์ใช้หาระยะห่างทางวิวัฒนาการของการกลายพันธุ์แบบหมุนวนสำหรับสายพันธุกรรมที่มีการซ้ำซ้อนกันของยีน ดังนั้นวิทยานิพนธ์นี้จีงเป็นการขยายแนวคิดของ Hannenhalli และ Pevzner สำหรับสายพันธุกรรมที่มีการซ้ำซ้อนกันของยีน ซึ่งเป็นการนำเสนอขั้นตอนวิธีใหม่ที่มีการเรียนรู้ด้วยตัวเอง (heuristic) เพื่อใช้ในการคำนวณหาระยะห่างทางวิวัฒนาการของการกลายพันธุ์แบบหมุนวนสำหรับสายพันธุกรรมที่มีการซ้ำซ้อนกันของยีน โดยใช้หลักการของไบนารีอินทีเจอร์โปรแกรมมิ่ง (Binary Integer Programming) นอกจากนี้เราสามารถนำมาประยุกต์ใช้ในการหาระยะห่างทางวิวัฒนาการของการกลายพันธุ์แบบแทรก และการกลายพันธุ์แบบการหมุนวนและแทรก ผลการทดลองจากข้อมูลที่สร้างขึ้นเองและข้อมูลจริงในทางชีววิทยา พบว่าวิธีการที่นำเสนอนี้สามารถคำนวณหาระยะห่างทางวิวัฒนาการของการกลายพันธุ์แบบหมุนวนได้อย่างถูกต้องแม่นยำ.

Chulalongkorn University. Center of Academic Resources

Address: BANGKOK

Email: cuir@car.chula.ac.th

Name: Chidchanok Lursinsap

Role: advisor

Created: 2005

Modified: 2011-04-29

Issued: 2011-04-29

วิทยานิพนธ์/Thesis

application/pdf

ISBN: 9745325309

eng

DegreeName: Doctor of Philosophy

Level: Doctoral Degree

Descipline: Mathematics

Grantor: Chulalongkorn University

©copyrights Chulalongkorn University

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	jakkarin.pdf	4.96 MB	14	2018-05-13 15:50:13

ใช้เวลา

0.025132 วินาที