Isomorphism and similarity for 2-generation pedigrees.
BMC Bioinformatics
; 16 Suppl 5: S7, 2015.
Article
en En
| MEDLINE
| ID: mdl-25860335
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.
Texto completo:
1
Colección:
01-internacional
Base de datos:
MEDLINE
Asunto principal:
Linaje
/
Algoritmos
/
Simulación por Computador
/
Biología Computacional
Límite:
Female
/
Humans
/
Male
Idioma:
En
Revista:
BMC Bioinformatics
Asunto de la revista:
INFORMATICA MEDICA
Año:
2015
Tipo del documento:
Article