วัชรพัฐ เมตตานันท

My Profile

Name: Top Vacharapat Mettanant

E-Mail Address: kidkus28@hotmail.com

Research Lab: Theory Research Group

Web Site: http://kidkus28.multiply.com

Research Interests: Algorithms on Computational Biology, Algorithms on Strings, Approximation Algorithms

More Interests: Classical Music, Novels, Physics

Research Topic

Recently focused

• Maximum Asymmetric Traveling Salesman Problem
• Shortest Superstring Problem
• Algorithms for Genome Reconstruction
• Approximation Algorithms for Tree Alignment

Currently focused

• Algorithms for Haplotype Inference Problems
• Inferring gene orders from gene maps using the breakpoint distance

Notes

Haplotype Inference Problem

Description

A haplotype is a DNA sequence that has been inherited from one parent. Each person possesses two haplotypes for most regions of the genome. The most common type of variation among haplotypes possessed by individuals in a population is the single nucleotide polymorphism (SNP), which can be represented by the vector pattern. Nowadays, one of the current priorities in human genomics is the development of a full Haplotype Map of the human genome, to be used in large-scale screens of populations. In this endeavor, a key problem is to infer haplotype pairs or haplotype frequencies from genotype data, since collecting haplotype data is generally more difficult than collecting genotype data. This is called the Haplotype Inference (HI) problem.

In order to have a hope of finding the haplotypes that actually generated the observed genotypes, we must use some genetic model of the evolution of the underlying haplotypes. There are two major approaches for solving the problem: combinatorial methods and statistical methods. Combinatorial methods often state an explicit objective function that one tries to optimize in order to obtain a solution to the inference problem. Statistical methods are usually based on an explicit model of haplotype evolution; the inference problem is then cast as a maximum-likelihood or a Bayesian inference problem.

Major sources of information

• The homepage of Dan Gusfield, http://wwwcsif.cs.ucdavis.edu/~gusfield/paperlist.html
• The homepage of Eran Halperin, http://www.icsi.berkeley.edu/~heran/publications/research.htm
• The homepage de Anne Bergeron, http://www.lacim.uqam.ca/~anne/
• The homepage of Nadia El-Mabrouk, http://www.iro.umontreal.ca/~mabrouk/
• Journal of Computational Biology http://www.liebertonline.com/loi/cmb
• The American Journal of Human Genetics, http://www.journals.uchicago.edu/AJHG/home.html
• Association for Computing Machinery (ACM), http://www.acm.org/
• International Conference on Research in Computational Molecular Biology (RECOMB)
• Springer, http://www.springer.com

Best introduction to the topic

• Haplotype Inference D. Gusfield and S.H. Orzack, In CRC Handbook on Bioinformatics, 2005 (S. Aluru Editor)

Inferring gene orders from gene maps using the breakpoint distance

เกี่ยวกับปัญหา

จาก paper

• G. Blin, E. Blais, P. Guillon, M. Blanchette and N. El-Mabrouk. Inferring Gene Orders from Gene Maps using the Breakpoint Distance. Fourth RECOMB Comparative Genomics Satellite Workshop. LNCS/LNBI 4205, pp. 99-112, 2006. (pdf)

โมเดลปัญหา Given: partial order 'P' (เป็น DAG) และ total order 'O' (เป็น sequence) บนเซตของ genes {1,2,...,n} (โดยปรกติจะให้ O เป็น 123...n ไปเลย) Find: Order O' (เป็น sequence) ที่ไม่ขัดแย้งกับ P และใกล้เคียงกับ O มากที่สุด นั่นคือ มี breakpoint น้อยที่สุด

ผลจาก paper ข้างต้น

• ปัญหา MBL (Mimimum-Breakpoint Linearization) เป็น NP-complete โดยทำ reduction จาก Independent Set
• dynamic programming algorithms ที่ใช้เวลาเป็น expo
• an efficient heuristic ที่ทำงานในเวลาพหุนาม และมีผลการทดลองดี 90% ขึ้น

บันทึกเพิ่มเติม

• heuristic จาก paper ข้างต้นให้ approx-factor เป็น O(n)

- จากตัวปัญหา จะได้ว่า factor ไม่เกิน n อยู่แล้ว

- มีกรณีที่ heuristic อัลกอให้คำตอบมากเป็น n/c เท่าของคำตอบที่ดีที่สุด สำหรับค่าคงที่ c

พิจารณา เมื่อ O= 123...17 และ P เป็น DAG ต่อไปนี้