A Stratified Sampling Scheme for Clique Estimation in Bait-Prey Graphs

• Activity Number: 165
• Type: Topic Contributed
• Date/Time: Monday, August 5, 2013 : 10:30 AM to 12:20 PM
• Sponsor: Biometrics Section
• Author(s): Denise Scholtens*+
• Companies: Northwestern University Medical School
• Keywords: graphs ; bait-prey ; sampling ; clique

Abstract

In cellular biology studies, node-and-edge graph or `network' data collection often proceeds using bait-prey technologies such as co-immunoprecipitation (CoIP) to assay relationships between protein pairs. CoIP specifically measures protein complex co-membership with a view to cataloging protein complex membership via clique estimation in the observed CoIP graph. Due to budgetary and other logistical constraints, exhaustive assay of the entire network using CoIP is often neither possible nor desirable. To effectively allocate resources for informative assay of portions of the graph for accomplishing clique estimation, we describe a stratified sampling experimental design scheme in which generalized nodes, defined as sets of adjacent nodes with identical adjacency outside the set, compose the strata. Strata are redefined at each round of sampling to incorporate accumulating data and clique estimates. We describe how this scheme maintains user-specified quality thresholds for the clique estimates and, relative to simple random sampling, leads to a marked increase in the number of correctly estimated cliques at each round of sampling.