Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Prediction of RNA secondary structure using evolutionary algorithm
Year (A.D.)
2018
Document Type
Thesis
First Advisor
ประภาส จงสถิตย์วัฒนา
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Computer Engineering (ภาควิชาวิศวกรรมคอมพิวเตอร์)
Degree Name
วิศวกรรมศาสตรดุษฎีบัณฑิต
Degree Level
ปริญญาเอก
Degree Discipline
วิศวกรรมคอมพิวเตอร์
DOI
10.58837/CHULA.THE.2018.1267
Abstract
วิทยานิพนธ์นี้นำเสนอขั้นตอนวิธีแบบใหม่ชื่อว่า Hybrid-EDAfold ซึ่งเป็นขั้นตอนวิธีเชิงวิวัฒนาการที่อยู่บนพื้นฐานของขั้นตอนวิธีประมาณการแจกแจงแบบผสมสำหรับทำนายโครงสร้างทุติยภูมิของอาร์เอ็นเอ ขั้นตอนวิธีที่นำเสนอประกอบด้วย 2 ขั้นตอนวิธีประมาณการแจกแจงและดำเนินการอยู่บนเทคนิคการทำนายโครงสร้างที่มีค่าพลังงานต่ำสุด ขั้นตอนวิธีที่นำเสนอใช้ทั้งกลุ่มคำตอบดีและกลุ่มคำตอบด้อยร่วมกันในการปรับปรุงแบบจำลองความน่าจะเป็นเพื่อส่งเสริมให้ขั้นตอนวิธีสามารถค้นหาได้ทั่วทั้งปริภูมิค้นหา ใช้ข้อมูลจากคำตอบด้อยเพื่อบ่งบอกว่าบริเวณไหนไม่น่าสนใจที่จะเข้าไปสำรวจเมื่อต้องดำเนินการกับข้อมูลที่มีจำนวนมิติที่ค่อนข้างสูง วิธีการที่นำเสนอมีการเพิ่มเติมตัวดำเนินการกลายพันธุ์ในขั้นตอนวิธีประมาณการแจกแจงหนึ่งเพื่อสนับสนุนการค้นหาแบบท้องถิ่น ช่วยเพิ่มความหลากหลายของคำตอบและบรรเทาการลู่เข้าก่อนกำหนด นอกจากนี้ วิธีการที่นำเสนอยังรองรับการทำนายหลายโครงสร้างทั้งโครงสร้างที่มีค่าพลังงานต่ำสุดและโครงสร้างที่มีค่าพลังงานต่ำรองเพื่อเพิ่มโอกาสที่จะพบโครงสร้างที่ใกล้เคียงกับโครงสร้างที่เป็นคำตอบมากยิ่งขึ้น การประเมินประสิทธิภาพของขั้นตอนวิธี Hybrid-EDAfold เมื่อเปรียบเทียบกับขั้นตอนวิธีในกลุ่มของกำหนดการพลวัตที่เป็นที่รู้จักกันดี ได้แก่ Mfold, RNAfold และ RNAstructure บนข้อมูลอาร์เอ็นเอจาก 15 ชนิด จำนวน 760 สายลำดับ พบว่า ขั้นตอนวิธี Hybrid-EDAfold มีผลการทำนายเฉลี่ยดีกว่าขั้นตอนวิธีอื่น ๆ ที่นำมาเปรียบเทียบในทุกตัวชี้วัด และ เปรียบเทียบกับขั้นตอนวิธีในกลุ่มเมตาฮิวริสติกด้วยอาร์เอ็นเอ 20 สายลำดับ ผลลัพธ์แสดงให้เห็นว่าวิธีการที่นำเสนอมีค่า F-measure เฉลี่ยดีกว่า RnaPredict และ SARNA-Predict และ มีผลลัพธ์เทียบเคียงได้กับ TL-PSOfold
Other Abstract (Other language abstract of ETD)
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.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
ศรีคำดี, สุภาวดี, "การทำนายโครงสร้างทุติยภูมิของอาร์เอ็นเอด้วยขั้นตอนวิธีเชิงวิวัฒนาการ" (2018). Chulalongkorn University Theses and Dissertations (Chula ETD). 3398.
https://digital.car.chula.ac.th/chulaetd/3398