The spreading of neurofibrillary tangles (NFTs), intraneuronal aggregates of highly phosphorylated microtubule-associated protein tau, across the human brain is correlated with the cognitive severity of Alzheimer's disease (AD). To identify genes relevant to NFT expansion defined by the Braak stage, we conducted whole-genome exon array analysis with an exploratory sample set consisting of 213 human post-mortem brain tissue specimens from the entorinal, temporal and frontal cortices of 71 brain-donor subjects: Braak NFT stages 0 (N = 13), I-II (N = 20), III-IV (N = 19) and V-VI (N = 19). We identified eight genes, RELN, PTGS2, MYO5C, TRIL, DCHS2, GRB14, NPAS4 and PHYHD1, associated with the Braak stage. The expression levels of three genes, PHYHD1, MYO5C and GRB14, exhibited reproducible association on real-time quantitative PCR analysis. In another sample set, including control subjects (N = 30), and in patients with late-onset AD (N = 37), dementia with Lewy bodies (N = 17) and Parkinson disease (N = 36), the expression levels of two genes, PHYHD1 and MYO5C, were obviously associated with late-onset AD. Protein-protein interaction network analysis with a public database revealed that PHYHD1 interacts with MYO5C via POT1, and PHYHD1 directly interacts with amyloid beta-peptide 42. It is thus likely that functional failure of PHYHD1 and MYO5C could lead to AD development.