Limits...
Isomorphism and similarity for 2-generation pedigrees.

Jiang H, Lin G, Tong W, Zhu D, Zhu B - BMC Bioinformatics (2015)

Bottom Line: If the 2-generation pedigrees are monogamous (i.e., each individual at level-1 can mate with exactly one partner) then the isomorphism testing problem can be solved in polynomial time.We then consider the problem by relaxing it into an NP-complete decomposition problem which can be formulated as the Minimum Common Integer Pair Partition (MCIPP) problem, which we show to be FPT by exploiting a property of the optimal solution.While there is still some difficulty to overcome, this lays down a solid foundation for this research.

View Article: PubMed Central - HTML - PubMed

ABSTRACT
We consider the emerging problem of comparing the similarity between (unlabeled) pedigrees. More specifically, we focus on the simplest pedigrees, namely, the 2-generation pedigrees. We show that the isomorphism testing for two 2-generation pedigrees is GI-hard. If the 2-generation pedigrees are monogamous (i.e., each individual at level-1 can mate with exactly one partner) then the isomorphism testing problem can be solved in polynomial time. We then consider the problem by relaxing it into an NP-complete decomposition problem which can be formulated as the Minimum Common Integer Pair Partition (MCIPP) problem, which we show to be FPT by exploiting a property of the optimal solution. While there is still some difficulty to overcome, this lays down a solid foundation for this research.

Show MeSH
A 2-generation pedigree, the right component is monogamous.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4402698&req=5

Figure 2: A 2-generation pedigree, the right component is monogamous.

Mentions: Let . An individual u ∈ I(P) is monogamous if it mates with exactly one partner, i.e., the number of individuals u', u' ≠ u, such that (u, x), (u', x) ∈ E(P) for some x ∈ I(P) is exactly one. A pedigree is monogamous if all the individuals are monogamous. In Figure 2, the sub-pedigree formed by the rightmost component is monogamous while the leftmost component is not. A pedigree P = (I(P), E(P)) is generational if there is a function such that:


Isomorphism and similarity for 2-generation pedigrees.

Jiang H, Lin G, Tong W, Zhu D, Zhu B - BMC Bioinformatics (2015)

A 2-generation pedigree, the right component is monogamous.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4402698&req=5

Figure 2: A 2-generation pedigree, the right component is monogamous.
Mentions: Let . An individual u ∈ I(P) is monogamous if it mates with exactly one partner, i.e., the number of individuals u', u' ≠ u, such that (u, x), (u', x) ∈ E(P) for some x ∈ I(P) is exactly one. A pedigree is monogamous if all the individuals are monogamous. In Figure 2, the sub-pedigree formed by the rightmost component is monogamous while the leftmost component is not. A pedigree P = (I(P), E(P)) is generational if there is a function such that:

Bottom Line: If the 2-generation pedigrees are monogamous (i.e., each individual at level-1 can mate with exactly one partner) then the isomorphism testing problem can be solved in polynomial time.We then consider the problem by relaxing it into an NP-complete decomposition problem which can be formulated as the Minimum Common Integer Pair Partition (MCIPP) problem, which we show to be FPT by exploiting a property of the optimal solution.While there is still some difficulty to overcome, this lays down a solid foundation for this research.

View Article: PubMed Central - HTML - PubMed

ABSTRACT
We consider the emerging problem of comparing the similarity between (unlabeled) pedigrees. More specifically, we focus on the simplest pedigrees, namely, the 2-generation pedigrees. We show that the isomorphism testing for two 2-generation pedigrees is GI-hard. If the 2-generation pedigrees are monogamous (i.e., each individual at level-1 can mate with exactly one partner) then the isomorphism testing problem can be solved in polynomial time. We then consider the problem by relaxing it into an NP-complete decomposition problem which can be formulated as the Minimum Common Integer Pair Partition (MCIPP) problem, which we show to be FPT by exploiting a property of the optimal solution. While there is still some difficulty to overcome, this lays down a solid foundation for this research.

Show MeSH