Mathematics – Combinatorics
Scientific paper
2006-09-10
SIAM Journal on Discrete Mathematics, vol 22, no. 3, pp. 961--970, 2008
Mathematics
Combinatorics
16 pages, 4 figures
Scientific paper
10.1137/060675964
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.
No associations
LandOfFree
Combinatorics of pedigrees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Combinatorics of pedigrees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorics of pedigrees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-658721