การทำนายโครงสร้างทุติยภูมิของอาร์เอ็นเอด้วยขั้นตอนวิธีเชิงวิวัฒนาการ

สุภาวดี ศรีคำดี

Please use this identifier to cite or link to this item: https://cuir.car.chula.ac.th/handle/123456789/61549

Title:	การทำนายโครงสร้างทุติยภูมิของอาร์เอ็นเอด้วยขั้นตอนวิธีเชิงวิวัฒนาการ
Other Titles:	Prediction of RNA secondary structure using evolutionary algorithm
Authors:	สุภาวดี ศรีคำดี
Advisors:	ประภาส จงสถิตย์วัฒนา
Other author:	จุฬาลงกรณ์มหาวิทยาลัย. คณะวิศวกรรมศาสตร์
Subjects:	อาร์เอ็นเอ อัลกอริทึม RNA Algorithms
Issue Date:	2561
Publisher:	จุฬาลงกรณ์มหาวิทยาลัย
Abstract:	วิทยานิพนธ์นี้นำเสนอขั้นตอนวิธีแบบใหม่ชื่อว่า Hybrid-EDAfold ซึ่งเป็นขั้นตอนวิธีเชิงวิวัฒนาการที่อยู่บนพื้นฐานของขั้นตอนวิธีประมาณการแจกแจงแบบผสมสำหรับทำนายโครงสร้างทุติยภูมิของอาร์เอ็นเอ ขั้นตอนวิธีที่นำเสนอประกอบด้วย 2 ขั้นตอนวิธีประมาณการแจกแจงและดำเนินการอยู่บนเทคนิคการทำนายโครงสร้างที่มีค่าพลังงานต่ำสุด ขั้นตอนวิธีที่นำเสนอใช้ทั้งกลุ่มคำตอบดีและกลุ่มคำตอบด้อยร่วมกันในการปรับปรุงแบบจำลองความน่าจะเป็นเพื่อส่งเสริมให้ขั้นตอนวิธีสามารถค้นหาได้ทั่วทั้งปริภูมิค้นหา ใช้ข้อมูลจากคำตอบด้อยเพื่อบ่งบอกว่าบริเวณไหนไม่น่าสนใจที่จะเข้าไปสำรวจเมื่อต้องดำเนินการกับข้อมูลที่มีจำนวนมิติที่ค่อนข้างสูง วิธีการที่นำเสนอมีการเพิ่มเติมตัวดำเนินการกลายพันธุ์ในขั้นตอนวิธีประมาณการแจกแจงหนึ่งเพื่อสนับสนุนการค้นหาแบบท้องถิ่น ช่วยเพิ่มความหลากหลายของคำตอบและบรรเทาการลู่เข้าก่อนกำหนด นอกจากนี้ วิธีการที่นำเสนอยังรองรับการทำนายหลายโครงสร้างทั้งโครงสร้างที่มีค่าพลังงานต่ำสุดและโครงสร้างที่มีค่าพลังงานต่ำรองเพื่อเพิ่มโอกาสที่จะพบโครงสร้างที่ใกล้เคียงกับโครงสร้างที่เป็นคำตอบมากยิ่งขึ้น การประเมินประสิทธิภาพของขั้นตอนวิธี Hybrid-EDAfold เมื่อเปรียบเทียบกับขั้นตอนวิธีในกลุ่มของกำหนดการพลวัตที่เป็นที่รู้จักกันดี ได้แก่ Mfold, RNAfold และ RNAstructure บนข้อมูลอาร์เอ็นเอจาก 15 ชนิด จำนวน 760 สายลำดับ พบว่า ขั้นตอนวิธี Hybrid-EDAfold มีผลการทำนายเฉลี่ยดีกว่าขั้นตอนวิธีอื่น ๆ ที่นำมาเปรียบเทียบในทุกตัวชี้วัด และ เปรียบเทียบกับขั้นตอนวิธีในกลุ่มเมตาฮิวริสติกด้วยอาร์เอ็นเอ 20 สายลำดับ ผลลัพธ์แสดงให้เห็นว่าวิธีการที่นำเสนอมีค่า F-measure เฉลี่ยดีกว่า RnaPredict และ SARNA-Predict และ มีผลลัพธ์เทียบเคียงได้กับ TL-PSOfold
Other Abstract:	This thesis proposed a new method namely Hybrid-EDAfold which is an evolutionary algorithm (EA) based on a hybrid estimation of distribution algorithms (EDAs) for RNA secondary structure prediction. The proposed method consists of two EDAs and using minimum free energy technique. The Hybrid-EDAfold uses both good and poor solutions enabling the algorithm to search throughout the search space. Using information from poor solutions can indicate which area is unappealing to explore when conducting a search with high-dimensional data. In addition, one of the EDA uses a mutation operator to support local search which increases the diversity and moderately avoid early convergence. Moreover, the proposed method returns the answer as a set of structures consisting of optimal structure and suboptimal structures to increase the chance of finding a predicted structure closer to the real structure. Comparison of the Hybrid-EDAfold was evaluated with well-known web servers namely Mfold, RNAfold, and RNAstructure on 15 RNA types with 760 RNA sequences total. The Hybrid-EDAfold yields better results than other methods in every metrics. The proposed method was also compared with metaheuristic methods on 20 RNA sequences collected from their literature. The results showed that the Hybrid-EDAfold yields better results than RnaPredict and SARNA-Predict and is comparable to TL-PSOfold.
Description:	วิทยานิพนธ์ (วศ.ด.)--จุฬาลงกรณ์มหาวิทยาลัย, 2561
Degree Name:	วิศวกรรมศาสตรดุษฎีบัณฑิต
Degree Level:	ปริญญาเอก
Degree Discipline:	วิศวกรรมคอมพิวเตอร์
URI:	http://cuir.car.chula.ac.th/handle/123456789/61549
URI:	http://doi.org/10.58837/CHULA.THE.2018.1267
metadata.dc.identifier.DOI:	10.58837/CHULA.THE.2018.1267
Type:	Thesis
Appears in Collections:	Eng - Theses

Files in This Item:

File	Description	Size	Format
5771474521.pdf		2.72 MB	Adobe PDF	View/Open

Show full item record