Constrained Mining of Minimal Separators with Applications to Gene Perturbation Studies
BackgroundIn studying complex biological systems, a key objective is to identify a set of gene to mutate for modifying certain functions or a behavior. An interesting question is which minimal set of genes should be knocked down/out in order to separate targeted biological sub-networks from others. In this paper, we present an algorithm to address precisely this question by leveraging results 1 on the connection between graph separators 2 and closed itemset 3 mining.Our specific contributions are: (a) we introduce the problem of mining constrained minimal separators,where some parts of the graph are intended to be disconnected from each other whereas others are expected to be as connected as possible; (b) we present an efficient algorithm to compute constrained minimal separators and prove its correctness theoretically. This algorithm transforms the given problem so that the computation is conducted over a much smaller graph than the original network of interactions; ? We apply our approach to phenotype modeling in S. Cerevisiae and C. Olegans. The predicted minimal separators are validated by published research.
Ying Jin Naren Ramakrishnan Lenwood S.Heath Richard F.Helm
Department of Computer Science, Virginia Tech, Blacksburg, VA, U.S.A. Department of Biochemistry, Virginia Tech, Blacksburg, VA, U.S.A.
国际会议
The 7th Asia-Pacific Bioinformatics Conference(第七届亚太生物信息学大会)
北京
英文
887
2009-01-01（万方平台首次上网日期，不代表论文的发表时间）