Chulalongkorn University Theses and Dissertations (Chula ETD)
Improvement of dynamic programming time for a long haplotype in the problem of haplotype inference on a pedigree containing some missing alleles
Other Title (Parallel Title in Other Language of ETD)
การปรับปรุงเวลาของกำหนดการพลวัตสำหรับแฮพลอไทป์ขนาดยาวในปัญหาการอนุมานแฮพลอไทป์ในพันธุประวัติที่มีการขาดหายของแอลลีล
Year (A.D.)
2004
Document Type
Thesis
First Advisor
Chidchanok Lursinsap
Faculty/College
Faculty of Science (คณะวิทยาศาสตร์)
Degree Name
Master of Science
Degree Level
Master's Degree
Degree Discipline
Computational Science
DOI
10.58837/CHULA.THE.2004.1116
Abstract
This study concerns with the problem of inferring haplotypes from a genotype data for each member in a pedigree using a minimum-recombinant criterion, which is useful for reducing the cost of typical laboratory techniques. Most available methods for finding the exact solutions of this problem showed the feasibility for only short haplotypes. Based on the recent method that uses a dynamic programming algorithm, we propose some improvements to make it feasible with long haplotypes and able to work with the data containing some missing alleles. Our improvements also allow the occurrence of a few Mendelian inconsistent alleles which can possibly appear in the data. The experimental results show that the computing time of our method outperforms the original method for the case of inferring long haplotypes (more than 20 loci) in a moderate-size pedigree (15-25 members)
Other Abstract (Other language abstract of ETD)
งานวิจัยนี้เกี่ยวข้องกับปัญหาการอนุมานแฮพลอไทป์จากข้อมูลจีโนไทป์ของสมาชิกแต่ละคนในพันธุ์ประวัติโดยใช้เกณฑ์การเกิดรีคอมบิเนชันน้อยที่สุดซึ่งมีประโยชน์ในการลดค่าใช้จ่ายของเทคนิคเชิงปฏิบัติการในทางตรง โดยส่วนใหญ่แล้ววิธีที่ใช้หาผลเฉลยแม่นตรงของปัญหาการอนุมานแฮพลอไทป์แบบนี้จะเหมาะสมกับแฮพลอไทป์ขนาดสั้นเท่านั้น จากงานวิจัยหนึ่งซึ่งใช้วิธีกำหนดการพลวัตในการแก้ปัญหานี้ เราได้นำเสนอการปรับปรุงบางอย่างเพื่อให้วิธีดังกล่าวมีความเหมาะสมกับการอนุมานแฮพลอไทป์ขนาดยาวและสามารถใช้กับข้อมูลที่มีการขาดหายของแอลลีล รวมทั้งยังมีการปรับปรุงให้ใช้ได้กับกรณีที่มีบางแอลลีลไม่สอดคล้องกับหลักการถ่ายทอดของเมนเดล ผลการทดลองแสดงให้เห็นว่าวิธีการที่นำเสนอให้ผลในแง่ของเวลาในการคำนวณดีกว่าวิธีเดิม เมื่อใช้กับการอนุมานแฮพลอไทป์ขนาดยาว (มากกว่า 20 ตำแหน่ง) ในพันธุประวัติขนาดปานกลาง (15-25 คน)
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
Kotcharat, Amares, "Improvement of dynamic programming time for a long haplotype in the problem of haplotype inference on a pedigree containing some missing alleles" (2004). Chulalongkorn University Theses and Dissertations (Chula ETD). 56276.
https://digital.car.chula.ac.th/chulaetd/56276