การประกอบชิ้นส่วนดีเอ็นเอแบบอัตโนมัติและเป็นลำดับโดยใช้กฎเมตาฮิวริสติก

Hierarchical automated DNA fragment assembly by Metaheuristics

Name: กัมพล สุกใส

ThaSH: ดีเอ็นเอ -- การวิเคราะห์

keyword: กฎเมตาฮิวริสติก

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

Abstract: DNA fragment assembly is an important step in genome sequencing projects. The assembly problem generally arises during the sequencing of large strands of DNA where the strands are needed to be shotgun-replicated and broken into fragments that are small enough for sequencing. The assembly problem can thus be classified as a combinatorial optimization problem where the aim is to find the right order and orientation of each fragment in the ordering layout that leads to the formation of a consensus sequence that truly reflects the original DNA strands. This thesis presents a metaheuristic procedure for the task where the procedure contains three main steps: fragment overlap score calculation, fragment layout determination and contiguous sequence (contig) construction. The overlap score is obtained from a Smith-Waterman algorithm while the score-based fragment layout including the order and orientation of each fragment is generated by a nearest neighbor heuristic rule and an ant colony system algorithm. With the availability of the fragment layout, contigs can be constructed where each contig can also be viewed as a new DNA fragment. As a result, the metaheuristic procedure can be recursively applied to the resulting contig sets. The experimental results indicate that the performance of the metaheuristic procedure is comparable to that of a CAP3 assembly program.

สถาบันเทคโนโลยีพระจอมเกล้าพระนครเหนือ. สำนักหอสมุดกลาง

Address: กรุงเทพมหานคร

Email: library@kmutnb.ac.th

Name: ณชล ไชยรัตนะ

Role: ที่ปรึกษาวิทยานิพนธ์

Email : nchl@kmitnb.ac.th

Created: 2549

Issued: 2550-12-20

Modified: 2567-06-10

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

CallNumber: วพ MEE ก394ส

tha

DegreeName: วิศวกรรมศาสตร์มหาบัณฑิต

Level: ปริญญาโท

Descipline: วิศวกรรมไฟฟ้า

Grantor: สถาบันเทคโนโลยีพระจอมเกล้าพระนครเหนือ

©copyrights มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าพระนครเหนือ

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	B14959902.pdf	754.69 KB

ใช้เวลา

0.016839 วินาที