Mathematical properties and bounds on haplotyping populations by pure parsimony

I. Lin Wang, Chia Yuan Chang

研究成果: Article同行評審

1 引文 斯高帕斯(Scopus)


Although the haplotype data can be used to analyze the function of DNA, due to the significant efforts required in collecting the haplotype data, usually the genotype data is collected and then the population haplotype inference (PHI) problem is solved to infer haplotype data from genotype data for a population. This paper investigates the PHI problem based on the pure parsimony criterion (HIPP), which seeks the minimum number of distinct haplotypes to infer a given genotype data. We analyze the mathematical structure and properties for the HIPP problem, propose techniques to reduce the given genotype data into an equivalent one of much smaller size, and analyze the relations of genotype data using a compatible graph. Based on the mathematical properties in the compatible graph, we propose a maximal clique heuristic to obtain an upper bound, and a new polynomial-sized integer linear programming formulation to obtain a lower bound for the HIPP problem.

頁(從 - 到)120-125
期刊Mathematical Biosciences
出版狀態Published - 2011 6月

All Science Journal Classification (ASJC) codes

  • 統計與概率
  • 建模與模擬
  • 一般生物化學,遺傳學和分子生物學
  • 一般免疫學和微生物學
  • 一般農業與生物科學
  • 應用數學


深入研究「Mathematical properties and bounds on haplotyping populations by pure parsimony」主題。共同形成了獨特的指紋。