TY - GEN

T1 - Identification of binary gene networks

AU - Birget, Jean Camille

AU - Lun, Desmond S.

AU - Wirth, Anthony

AU - Hong, Dawei

PY - 2012

Y1 - 2012

N2 - We continue our theoretical examination of the problem of gene network identification, which we introduced in a previous paper. Here we consider a purely binary model of gene networks, without the assumption of sensitivity side information made in our previous paper. We present the following somewhat intuitive result: A general acyclic binary gene network can be identified by a brute force approach (in which every assignment for all subsets of k genes is made, where k is the maximum number of genes by which a gene is controlled, followed by the measurement of steady-state expression response). Our proof shows that the result is not straightforward because of certain side-effects. We also describe a natural characterization of the set of non-acyclic networks that can be identified. Moreover, we show that without new assumptions, this brute force approach has optimal complexity in the worst case.

AB - We continue our theoretical examination of the problem of gene network identification, which we introduced in a previous paper. Here we consider a purely binary model of gene networks, without the assumption of sensitivity side information made in our previous paper. We present the following somewhat intuitive result: A general acyclic binary gene network can be identified by a brute force approach (in which every assignment for all subsets of k genes is made, where k is the maximum number of genes by which a gene is controlled, followed by the measurement of steady-state expression response). Our proof shows that the result is not straightforward because of certain side-effects. We also describe a natural characterization of the set of non-acyclic networks that can be identified. Moreover, we show that without new assumptions, this brute force approach has optimal complexity in the worst case.

UR - http://www.scopus.com/inward/record.url?scp=84875721496&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875721496&partnerID=8YFLogxK

U2 - 10.1109/Allerton.2012.6483392

DO - 10.1109/Allerton.2012.6483392

M3 - Conference contribution

AN - SCOPUS:84875721496

SN - 9781467345385

T3 - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012

SP - 1467

EP - 1474

BT - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012

T2 - 2012 50th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2012

Y2 - 1 October 2012 through 5 October 2012

ER -