Biology Reference
In-Depth Information
We conjecture that m is 2 for acyclic diversity graphs, which means
that the pure parsimony problem is solve by Algorithm 6.1. This together
with a proof of Conjecture 6.1 may highlight the class of diversity graphs
for which m =2.
Decomposing the genotypes into chains ordered by
bounds the opti-
mal value of the pure parsimony problem, but this bound can likely be
reduced by investigating how the solutions to the individual chains can
interact. Moreover, we do not yet know how to decompose the genotypes
into the fewest number of chains. This bound could be useful in the
integer programming formulation of the problem, and numerical work
should be explored.
Investigating how φ ( m ) decreases and estimating m are exciting new
avenues. If we can accomplish both of these, then we will be able to
estimate the solution to the pure parsimony problem.
References
[1]
A. S. Asratian, T. M. J. Denley, and R. Haggkvist. Bipartite Graphs and Their Appli-
cations . Cambridge University, New York, NY, 1998.
[2]
V. Bafna, D. Gusfield, G. Lancia, and S. Yooseph. Haplotyping as perfect phylogeny:
A direct approach. Technical Report CSE-2002-21, University of California, Davis,
Computer Science, 2002. Augmented version to appear in the Journal of Computa-
tional Biology.
[3]
R. H. Chung and D. Gusfield. Empirical exploration of perfect phylogeny haplotyping
and haplotypers. Technical report, University of California, Computer Science, 2003.
To appear in the Proceedings of the 2003 Cocoon Conference.
[4]
R. H. Chung and D. Gusfield. Perfect phylogeny haplotyper: Haplotype inferral using
a tree model. Bioinformatics , 19(6):780-781, 2003.
[5]
A. G. Clark. Inference of haplotypes from PCR-amplified samples of diploid popula-
tions. Molecular Biology and Evolution , 7(2):111-122, 1990.
[6]
D. Gusfield. A practical algorithm for optimal inference of haplotypes from diploid
populations. Proceedings of the Eight International Conference on Intelligent Sys-
tems for Molecular Biology , 2000.
[7]
D. Gusfield. Inference of haplotypes from samples of diploid populations: Complex-
ity and algorithms. Journal of Computational Biology , 8(3):305-324, 2001.
[8]
D. Gusfield. Haplotyping as perfect phylogeny: Conceptual framework and efficient
solutions. Proceedings of RECOMB 2002: The Sixth Annual International Confer-
ence on Computational Biology , pages 166-175, 2002.
[9]
D. Gusfield. Haplotyping by pure parsimony. Technical Report CSE-2003-2, Univer-
sity of California, Davis, 2003. To appear in the Proceedings of the 2003 Combina-
torial Pattern Matching Conference.
[10]
G. Lancia, V. Bafna, S. Istrail, R. Lippert, and R. Schwartz. SNPs problems, complex-
Search WWH ::




Custom Search