×

A sequential algorithm for false discovery rate control on directed acyclic graphs. (English) Zbl 1506.62312

Summary: We propose a linear-time, single-pass, top-down algorithm for multiple testing on directed acyclic graphs, where nodes represent hypotheses and edges specify a partial ordering in which the hypotheses must be tested. The procedure is guaranteed to reject a sub-directed acyclic graph with bounded false discovery rate while satisfying the logical constraint that a rejected node’s parents must also be rejected. It is designed for sequential testing settings where the directed acyclic graph structure is known a priori but the \(p\)-values are obtained selectively, such as in a sequence of experiments; however, the algorithm is also applicable in nonsequential settings where all \(p\)-values can be calculated in advance, such as in model selection. Our algorithm provably controls the false discovery rate under independence, positive dependence or arbitrary dependence of the \(p\)-values and specializes to known algorithms in the special cases of trees and line graphs; it simplifies to the classical Benjamini-Hochberg procedure when the directed acyclic graph has no edges. We explore the empirical performance of our algorithm through simulations and analysis of a real dataset corresponding to a gene ontology, and we demonstrate its favourable performance in terms of computational time and power.

MSC:

62H15 Hypothesis testing in multivariate analysis
05C20 Directed graphs (digraphs), tournaments
62J15 Paired and multiple comparisons; multiple testing
62P10 Applications of statistics to biology and medical sciences; meta analysis
PDFBibTeX XMLCite
Full Text: DOI Link