TY - GEN

T1 - Computational experiments on algorithms for haplotype inference problems by pure parsimony

AU - Wang, I. Lin

AU - Yang, Hui E.

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2006

Y1 - 2006

N2 - To analyze the function of DNA, researchers have to obtain each haplotype, the genetic constitution of an individual chromosome, of an individual for analysis. Due to the significant efforts required in collecting haplotypes, the descriptions of one conflated pair of haplotypes called genotypes are usually collected. Since the genotype data contains insufficient information to identify the combination of DNA sequence in each copy of a chromosome, one has to solve the population haplotype inference problem by pure parsimony criterion which uses the minimum number of haplotypes to infer the haplotype data from genotype data for a population. Previous researches use mathematical programming methods such as integer programming and semidefinite programming models to solve the population haplotype inference problem. However, no computational experiment has ever been conducted to evaluate the algorithmic effectiveness. This paper thus conducts the first computational experiments on four haplotyping algorithms, including our new greedy heuristic and three pervious haplotyping algorithms.

AB - To analyze the function of DNA, researchers have to obtain each haplotype, the genetic constitution of an individual chromosome, of an individual for analysis. Due to the significant efforts required in collecting haplotypes, the descriptions of one conflated pair of haplotypes called genotypes are usually collected. Since the genotype data contains insufficient information to identify the combination of DNA sequence in each copy of a chromosome, one has to solve the population haplotype inference problem by pure parsimony criterion which uses the minimum number of haplotypes to infer the haplotype data from genotype data for a population. Previous researches use mathematical programming methods such as integer programming and semidefinite programming models to solve the population haplotype inference problem. However, no computational experiment has ever been conducted to evaluate the algorithmic effectiveness. This paper thus conducts the first computational experiments on four haplotyping algorithms, including our new greedy heuristic and three pervious haplotyping algorithms.

UR - http://www.scopus.com/inward/record.url?scp=33847737298&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847737298&partnerID=8YFLogxK

U2 - 10.2991/jcis.2006.243

DO - 10.2991/jcis.2006.243

M3 - Conference contribution

AN - SCOPUS:33847737298

SN - 9078677015

SN - 9789078677017

T3 - Proceedings of the 9th Joint Conference on Information Sciences, JCIS 2006

BT - Proceedings of the 9th Joint Conference on Information Sciences, JCIS 2006

T2 - 9th Joint Conference on Information Sciences, JCIS 2006

Y2 - 8 October 2006 through 11 October 2006

ER -