Secondly, PNAS is a good journal, but not a great one. He was almost certainly rejected from the top tier. (Nature, Science)
As someone who works in this field, finding genes that are similar in some way to two disease related genes is not at all novel. This is the goal of literally hundreds of computational methods. It sounds like what he did was to build a decision tree from a set of training data - hardly an earth-shattering application.
Edit: Wow, after fully reading the paper I am stunned how commonplace this analysis is. This exact approach has been taken for analyzing microarray data for the last decade. This does not warrant in any way the breathless writeup it receives in the original post.
Under what hypothesis would one expect nature to follow boolean rules? This approach ignores any subtle relationships or multifactorial causes of gene expression changes. The more I read the more I am convinced that this is utter garbage.
What really makes me mad about this is that increasingly the way to get ahead in science is to overstate your results and then have friends of the corresponding author "review" the manuscript. If you'll notice, this was submitted by Irving L Weissman who, according to his website is "Director, Institute of Stem Cell Biology and Regenerative Medicine, Stanford University School of Medicine". It is very odd that it wasn't submitted by either the corresponding, nor the lead author. It is very clear that this article did not receive the scientific scrutiny that it should have.