AbstractThe human virome, or the viral communities distributed on or in our body, is estimated to contain about 380 trillion of viruses (individuals), which has far reaching influences on our health and diseases. Obviously, the sheer numbers of viruses alone make the comparisons of two or multiple viromes extremely challenging. In fact, the theory of computation in computer science for so‐termed NP‐hard problems stipulates that the problem is unsolvable when the size of virome is sufficiently large even with fastest supercomputers. Practically, one has to develop heuristic and approximate algorithms to obtain practically satisfactory solutions for NP‐hard problems. Here, we extend the species‐specificity and specificity‐diversity framework to develop a method for virome comparison (VC). The VC method consists of a pair of metrics: virus species specificity (VS) and virome specificity diversity (VSD) and corresponding pair of random search algorithms. Specifically, the VS and VS permutation (VSP) test can detect unique virus species (US) or enriched virus species (ES) in each virome (treatment), and the VSD and VSD permutation (VSDP) test can further determine holistic differences between two viromes or their subsets (assemblages of viruses). The test with four virome data sets demonstrated that the VC method is effective, efficient, and robust.