การออกแบบและวิเคราะห์ขั้นตอนวิธีสำหรับสายอักขระและลำดับ

บทคัดย่อ

โครงการวิจัยนี้นำเสนอพัฒนาอัลกอริทึมสำหรับปัญหาการคัดลอกหลายยีน (the Multiple Gene Duplication Problem) ที่ทำงานในเวลาที่เป็นเชิงเส้นกับขนาดของปัญหา อัลกอริทึมดังกล่าวปรับปรุงประสิทธิภาพของอัลกอริทึมที่เสนอโดย Bansal และ Eulenstein ซึ่งใช้เวลาการทำงานเป็นกำลังสอง (quadratic time) ภายใต้การทดลองบนข้อมูลสังเคราะห์พบว่าอัลกอริทึมสามารถทำงานได้เร็วกว่าอัลกอริทึมเดิมมากกว่าสองเท่าเมื่อจำนวนสปีชีส์ในการทดลองมีค่ามากระดับหนึ่ง (ประมาณ 500 สปีชีส์) ผู้วิจัยได้พัฒนาโปรแกรมคอมพิวเตอร์ของอัลกอริทึมที่นำเสนอและได้เผยแพร่เป็นซอฟต์แวร์รหัสเปิด รวมทั้งได้พัฒนาโปรแกรมประยุกต์บนเว็บสำหรับทดลองใช้อัลกอริทึมดังกล่าวด้วยโครงการวิจัยนี้นำเสนอพัฒนาอัลกอริทึมสำหรับปัญหาการคัดลอกหลายยีน (the Multiple Gene Duplication Problem) ที่ทำงานในเวลาที่เป็นเชิงเส้นกับขนาดของปัญหา อัลกอริทึมดังกล่าวปรับปรุงประสิทธิภาพของอัลกอริทึมที่เสนอโดย Bansal และ Eulenstein ซึ่งใช้เวลาการทำงานเป็นกำลังสอง (quadratic time) ภายใต้การทดลองบนข้อมูลสังเคราะห์พบว่าอัลกอริทึมสามารถทำงานได้เร็วกว่าอัลกอริทึมเดิมมากกว่าสองเท่าเมื่อจำนวนสปีชีส์ในการทดลองมีค่ามากระดับหนึ่ง (ประมาณ 500 สปีชีส์) ผู้วิจัยได้พัฒนาโปรแกรมคอมพิวเตอร์ของอัลกอริทึมที่นำเสนอและได้เผยแพร่เป็นซอฟต์แวร์รหัสเปิด รวมทั้งได้พัฒนาโปรแกรมประยุกต์บนเว็บสำหรับทดลองใช้อัลกอริทึมดังกล่าวด้วย

คำสำคัญ