Diagnostic genes are usually used to distinguish different disease phenotypes. Most existing methods for diagnostic genes finding are based on either the individual or combinatorial discriminative power of gene(s). However, they both ignore the common expression trends among genes. In this paper, we devise a novel sequence rule, namely, top- k irreducible covering contrast sequence rules (Top kIRs for short), which helps to build a sample classifier of high accuracy. Furthermore, we propose an algorithm called MineTop kIRs to efficiently discover Top kIRs. Extensive experiments conducted on synthetic and real datasets show that MineTop kIRs is significantly faster than the previous methods and is of a higher classification accuracy. Additionally, many diagnostic genes discovered provide a new insight into disease diagnosis.