Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)

Computational Experiments on Algorithms for Haplotype Inference Problems by Pure Parsimony

Authors
I-Lin Wang1, Hui-E Yang
1Department of Industrial and Information Management
Corresponding Author
I-Lin Wang
Available Online October 2006.
DOI
10.2991/jcis.2006.243How to use a DOI?
Keywords
Haplotype inference, Genotype, Pure parsimony, Mathematical programming, Heuristic
Abstract

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, genotypes, which are the descriptions of one conflated pair of haplotypes, 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 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, dynamic 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.

Copyright
© 2006, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)
Series
Advances in Intelligent Systems Research
Publication Date
October 2006
ISBN
10.2991/jcis.2006.243
ISSN
1951-6851
DOI
10.2991/jcis.2006.243How to use a DOI?
Copyright
© 2006, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - I-Lin Wang
AU  - Hui-E Yang
PY  - 2006/10
DA  - 2006/10
TI  - Computational Experiments on Algorithms for Haplotype Inference Problems by Pure Parsimony
BT  - Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)
PB  - Atlantis Press
SP  - 307
EP  - 310
SN  - 1951-6851
UR  - https://doi.org/10.2991/jcis.2006.243
DO  - 10.2991/jcis.2006.243
ID  - Wang2006/10
ER  -