A sequential algorithm for false discovery rate control on directed acyclic graphs

Aaditya Ramdas, Jianbo Chen, Martin J Wainwright and Michael I Jordan

Biometrika, 2019, vol. 106, issue 1, 69-86

Abstract: 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.

Keywords: Directed acyclic graph; False discovery rate; Familywise error rate; Multiple testing; Partially ordered hypothesis; Sequential experimentation (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1093/biomet/asy066 (application/pdf)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:oup:biomet:v:106:y:2019:i:1:p:69-86.

Ordering information: This journal article can be ordered from
https://academic.oup.com/journals

Access Statistics for this article

Biometrika is currently edited by Paul Fearnhead

More articles in Biometrika from Biometrika Trust Oxford University Press, Great Clarendon Street, Oxford OX2 6DP, UK.
Bibliographic data for series maintained by Oxford University Press ().