← งานวิจัย COINล้างคิวทั้งหมดEnglish
COIN · ROSE · PERMUTATION OPTIMIZATION

ห้องทดลองเลือก Helix
สำหรับ DNA และ RNA

เปลี่ยน candidate stems ให้เป็น conflict graph แล้วใช้ permutation เป็นลำดับความสำคัญในการเลือกชุด helix ที่ไม่ใช้ nucleotide ซ้ำและไม่ตัดกัน เปรียบเทียบเสถียรภาพ coverage ความเรียบง่าย และช่วงการจับคู่ด้วย Pareto optimization

ตัวประเมินเดียว · งบเท่ากันทุกอัลกอริทึมใช้ instance, evaluator, seed และจำนวน objective evaluations เดียวกัน ผลลัพธ์จึงตรวจสอบและทำซ้ำได้
StatusReady
Runs completed0 / 0
Evaluations—
Best primary—

Benchmark

ผลจะปรากฏหลังการทดลอง

Current: —

บทนำและแนวคิดของปัญหา

ลำดับ nucleic acid หนึ่งสายสามารถสร้าง helix ที่เป็นไปได้จำนวนมาก แต่ candidate สองตัวอาจใช้ nucleotide ตำแหน่งเดียวกันหรือเกิด crossing pair ที่ dot-bracket แบบ nested แทนไม่ได้ ปัญหาจึงไม่ใช่เพียง “หา helix ที่ดีที่สุด” แต่คือ เลือก subset ของ helix ที่เข้ากันได้

Lab เชื่อม ViennaRNA เข้ามาเป็น physical evaluator แล้ว: COIN, ROSE และอัลกอริทึมเปรียบเทียบยังเป็นผู้สร้างโครงสร้าง ส่วน ViennaRNA ให้คะแนน dot-bracket แต่ละแบบด้วย Turner nearest-neighbor free energy ค่า pairing energy เดิมยังอยู่เป็น proxy ราคาถูกสำหรับ screening และการทดลองเปรียบเทียบ convergence การประเมิน Turner เปิดเฉพาะ RNA และ cache ตาม dot-bracket จึงไม่คำนวณ phenotype ที่ซ้ำกันใหม่

การแทนคำตอบ

π = (h₇,h₂,h₉,…,h₁)
selected ← ∅
for h in π: ถ้า conflict(h,selected)=0 ให้รับ h

candidate helix แต่ละตัวเป็น node ใน conflict graph และ edge หมายถึงใช้ nucleotide ซ้ำหรือ crossing กัน permutation เป็น priority order: ตัวที่มาก่อนมีสิทธิ์เข้าชุดก่อน เมื่อรับแล้วจะ block เพื่อนบ้านที่ขัดแย้ง วิธีนี้เปลี่ยน permutation ทุกชุดเป็นคำตอบ feasible โดยไม่ต้องเก็บ binary chromosome หรือ repair

DNA ใช้ AT/TA และ GC/CG ส่วน RNA ใช้ AU/UA, GC/CG และ GU/UG wobble เมื่อได้ subset แล้ว pair table ถูกแปลงเป็น dot-bracket เพื่อให้ inspect และ export ได้

นิยามปัญหา วัตถุประสงค์ และการคำนวณ fitness

ให้ H เป็น candidate helices, xₕ=1 เมื่อ helix h ถูกเลือก, E เป็น conflict edges และ Pₕ เป็น base pairs ของ h

xₕ+xₖ ≤ 1 ∀(h,k)∈E
min fproxy = Σₕ xₕ proxyScore(h)
min fTurner = ΔGTurner(dot-bracket(x)) [kcal/mol] — RNA เท่านั้น
min funpaired = 1 − 2Σₕxₕ|Pₕ| / n
min fcount = Σₕxₕ
min fspan = (1/Σxₕ)Σₕxₕ(endₕ−startₕ)/n

Turner energy เรียก ViennaRNA fold_compound.eval_structure เพื่อให้คะแนนโครงสร้างที่ตัวค้นเสนอ ไม่ได้เรียก dynamic programming ให้ ViennaRNA สร้างคำตอบแทน ส่วน pairing energy เป็น proxy ที่เร็วกว่า, unpaired fraction เพิ่ม coverage, helix count ลด fragmentation และ span penalty เอนเอียงสู่ interaction ระยะใกล้ สามารถเลือกหลายแกนเพื่อศึกษาการ multi-objectivization ได้

ที่มาของ benchmark และวรรณกรรมที่เกี่ยวข้อง

แนวคิด permutation-based helix selection มีรากฐานชัดเจนในงานของ Wiese, Hendriks, Deschênes และคณะ ซึ่งอธิบาย RNA folding ว่าเป็นการเลือก subset ของ feasible helices ด้วย permutation GA งาน Chen, Le และ Maizel ก็สร้าง master list ของ stems แล้วเพิ่มเฉพาะ stem ที่ compatible ทีละขั้น ส่วนงาน bpRNA ใช้ maximum weighted independent subset เพื่อแยก nested structure ออกจาก pseudoknot segments

อัลกอริทึมที่ใช้กับปัญหากลุ่มนี้ประกอบด้วย dynamic programming สำหรับ nested RNA, maximum-weight independent set ใน conflict graph, integer programming, branch-and-bound, GA/SA, ant colony, estimation-of-distribution algorithms และ sampling จาก Boltzmann ensemble Contribution ของ lab นี้ไม่ใช่การแทน ViennaRNA แต่คือ test bed เดียวสำหรับศึกษาว่าโมเดล permutation learning แต่ละชนิดเรียน priority relation ระหว่าง competing helices ได้อย่างไร

เอกสารอ้างอิง

  1. Wiese, K.C. et al. (2003). A permutation-based genetic algorithm for the RNA folding problem. Biosystems, 72, 29–41. DOI.
  2. Chen, J.-H., Le, S.-Y. & Maizel, J.V. (2000). Prediction of common secondary structures of RNAs: a genetic algorithm approach. Nucleic Acids Research, 28(4), 991–999. DOI.
  3. Danaee, P. et al. (2018). bpRNA: large-scale automated annotation and analysis of RNA secondary structure. NAR, 46(11), 5381–5394.
  4. SantaLucia, J. (1998). A unified view of polymer, dumbbell, and oligonucleotide DNA nearest-neighbor thermodynamics. PNAS, 95, 1460–1465.