Consistency checking is a fundamental computational problem in genetics.Given a pedigree and information on the genotypes (of some) of the individuals in it, the aim ofconsistency checking is to determine whether thes...Consistency checking is a fundamental computational problem in genetics.Given a pedigree and information on the genotypes (of some) of the individuals in it, the aim ofconsistency checking is to determine whether these data are consistent with the classic Mendelianlaws of inheritance. This problem arose originally from the geneticists'' need to filter their inputdata from erroneous information, and is well motivated from both a biological and a sociologicalviewpoint. This paper shows that consistency checking is NP-complete, even with focus on a singlegene and in the presence of three alleles. Several other results on the computational complexity ofproblems from genetics that are related to consistency checking are also offered. In particular, itis shown that checking the consistency of pedigrees over two alleles, and of pedigrees withoutloops, can be done in polynomial time.展开更多
The Graph isomorphism problem involves determining whether two graphs are isomorphic and the computational complexity required for this determination.In general,the problem is not known to be solvable in polynomial ti...The Graph isomorphism problem involves determining whether two graphs are isomorphic and the computational complexity required for this determination.In general,the problem is not known to be solvable in polynomial time,nor to be NP-complete.In this paper,by analyzing the algebraic properties of the adjacency matrices of the undirected graph,we first established the connection between graph isomorphism and matrix row and column interchanging operations.Then,we prove that for undirected graphs,the complexity in determining whether two graphs are isomorphic is at most O(n^(3)).展开更多
文摘Consistency checking is a fundamental computational problem in genetics.Given a pedigree and information on the genotypes (of some) of the individuals in it, the aim ofconsistency checking is to determine whether these data are consistent with the classic Mendelianlaws of inheritance. This problem arose originally from the geneticists'' need to filter their inputdata from erroneous information, and is well motivated from both a biological and a sociologicalviewpoint. This paper shows that consistency checking is NP-complete, even with focus on a singlegene and in the presence of three alleles. Several other results on the computational complexity ofproblems from genetics that are related to consistency checking are also offered. In particular, itis shown that checking the consistency of pedigrees over two alleles, and of pedigrees withoutloops, can be done in polynomial time.
基金supported in part by the U.S.National Science Foundation(CCF1919154 and ECCS-1923409).
文摘The Graph isomorphism problem involves determining whether two graphs are isomorphic and the computational complexity required for this determination.In general,the problem is not known to be solvable in polynomial time,nor to be NP-complete.In this paper,by analyzing the algebraic properties of the adjacency matrices of the undirected graph,we first established the connection between graph isomorphism and matrix row and column interchanging operations.Then,we prove that for undirected graphs,the complexity in determining whether two graphs are isomorphic is at most O(n^(3)).
