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

• 成果类型: Article
• 署名作者: Ramdas, Aaditya; Chen, Jianbo; Wainwright, Martin J.; Jordan, Michael I.
• 署名单位: Carnegie Mellon University; University of California System; University of California Berkeley
• 刊物名称: BIOMETRIKA
• ISSN/ISSBN: 0006-3444
• DOI: 10.1093/biomet/asy066
• 发表日期: 2019
• 页码: 6986
• 关键词: hypotheses; tests

摘要

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 -values are obtained selectively, such as in a sequence of experiments; however, the algorithm is also applicable in nonsequential settings where all -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 -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.