Combinatorics of Pedigrees I: Counterexamples to a Reconstruction Question

DOI10.1137/060675964MaRDI QIDQ3393428zbMATH OpenOpenAlexWikidataFDO

Authors Bhalchandra D. Thatte

Publication date 20 August 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0609264

zbMATH Keywords

reconstructionpedigrees

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A pedigree is a directed graph in which each vertex (except the founder vertices) has two parents. The main result in this paper is a construction of an infinite family of counter examples to a reconstruction problem on pedigrees, thus negatively answering a question of Steel and Hein. Some positive reconstruction results are also presented. The problem of counting distinct (mutually non-isomorphic) pedigrees is considered. The known lower and upper bounds on the number of pedigrees are improved upon, and their relevance to pedigree reconstruction from DNA sequence data is discussed. It is shown that the information theoretic bound on the number of segregating sites in the sequence data that is minimally essential for reconstructing pedigrees would not significantly change with improved enumerative estimates.

Recommendations

• Reconstructing pedigrees: a combinatorial perspective
• Reconstructing pedigrees: a stochastic perspective
• Reconstructing pedigrees: Some identifiability questions for a recombination-mutation model
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Efficient maximum likelihood pedigree reconstruction

Cited in

(7)

• Not all phylogenetic networks are leaf-reconstructible
• Leaf-reconstructibility of phylogenetic networks
• Reconstructing pedigrees: a stochastic perspective
• Reconstructing pedigrees: Some identifiability questions for a recombination-mutation model
• Reconstructing pedigrees: a combinatorial perspective
• The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)
• The largest strongly connected component in the cyclical pedigree model of Wakeley et al.

This page was built for publication: Combinatorics of Pedigrees I: Counterexamples to a Reconstruction Question

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3393428)