Approximate kernel reconstruction for time-varying networks

Gregory Ditzler, Nidhal Bouaynaya, Roman Shterenberg, Hassan M. Fathallah-Shaykh

Research output: Contribution to journalArticle

Abstract

Background: Most existing algorithms for modeling and analyzing molecular networks assume a static or time-invariant network topology. Such view, however, does not render the temporal evolution of the underlying biological process as molecular networks are typically "re-wired" over time in response to cellular development and environmental changes. In our previous work, we formulated the inference of time-varying or dynamic networks as a tracking problem, where the target state is the ensemble of edges in the network. We used the Kalman filter to track the network topology over time. Unfortunately, the output of the Kalman filter does not reflect known properties of molecular networks, such as sparsity. Results: To address the problem of inferring sparse time-varying networks from a set of under-sampled measurements, we propose the Approximate Kernel RecONstruction (AKRON) Kalman filter. AKRON supersedes the Lasso regularization by starting from the Lasso-Kalman inferred network and judiciously searching the space for a sparser solution. We derive theoretical bounds for the optimality of AKRON. We evaluate our approach against the Lasso-Kalman filter on synthetic data. The results show that not only does AKRON-Kalman provide better reconstruction errors, but it is also better at identifying if edges exist within a network. Furthermore, we perform a real-world benchmark on the lifecycle (embryonic, larval, pupal, and adult stages) of the Drosophila Melanogaster. Conclusions: We show that the networks inferred by the AKRON-Kalman filter are sparse and can detect more known gene-to-gene interactions for the Drosophila melanogaster than the Lasso-Kalman filter. Finally, all of the code reported in this contribution will be publicly available.

Original languageEnglish (US)
Article number5
JournalBioData Mining
Volume12
Issue number1
DOIs
StatePublished - Feb 6 2019

Fingerprint

Time varying networks
Kalman filters
Time-varying
Kalman Filter
kernel
Lasso
Drosophila melanogaster
Drosophilidae
Genes
Topology
Network Topology
Biological Phenomena
Benchmarking
Gene
Dynamic Networks
Synthetic Data
Sparsity
Life Cycle
Optimality
Regularization

All Science Journal Classification (ASJC) codes

  • Biochemistry
  • Molecular Biology
  • Genetics
  • Computer Science Applications
  • Computational Theory and Mathematics
  • Computational Mathematics

Cite this

Ditzler, Gregory ; Bouaynaya, Nidhal ; Shterenberg, Roman ; Fathallah-Shaykh, Hassan M. / Approximate kernel reconstruction for time-varying networks. In: BioData Mining. 2019 ; Vol. 12, No. 1.
@article{9e04dc868467434489fcfbea9fdba8aa,
title = "Approximate kernel reconstruction for time-varying networks",
abstract = "Background: Most existing algorithms for modeling and analyzing molecular networks assume a static or time-invariant network topology. Such view, however, does not render the temporal evolution of the underlying biological process as molecular networks are typically {"}re-wired{"} over time in response to cellular development and environmental changes. In our previous work, we formulated the inference of time-varying or dynamic networks as a tracking problem, where the target state is the ensemble of edges in the network. We used the Kalman filter to track the network topology over time. Unfortunately, the output of the Kalman filter does not reflect known properties of molecular networks, such as sparsity. Results: To address the problem of inferring sparse time-varying networks from a set of under-sampled measurements, we propose the Approximate Kernel RecONstruction (AKRON) Kalman filter. AKRON supersedes the Lasso regularization by starting from the Lasso-Kalman inferred network and judiciously searching the space for a sparser solution. We derive theoretical bounds for the optimality of AKRON. We evaluate our approach against the Lasso-Kalman filter on synthetic data. The results show that not only does AKRON-Kalman provide better reconstruction errors, but it is also better at identifying if edges exist within a network. Furthermore, we perform a real-world benchmark on the lifecycle (embryonic, larval, pupal, and adult stages) of the Drosophila Melanogaster. Conclusions: We show that the networks inferred by the AKRON-Kalman filter are sparse and can detect more known gene-to-gene interactions for the Drosophila melanogaster than the Lasso-Kalman filter. Finally, all of the code reported in this contribution will be publicly available.",
author = "Gregory Ditzler and Nidhal Bouaynaya and Roman Shterenberg and Fathallah-Shaykh, {Hassan M.}",
year = "2019",
month = "2",
day = "6",
doi = "10.1186/s13040-019-0192-1",
language = "English (US)",
volume = "12",
journal = "BioData Mining",
issn = "1756-0381",
publisher = "BioMed Central",
number = "1",

}

Approximate kernel reconstruction for time-varying networks. / Ditzler, Gregory; Bouaynaya, Nidhal; Shterenberg, Roman; Fathallah-Shaykh, Hassan M.

In: BioData Mining, Vol. 12, No. 1, 5, 06.02.2019.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Approximate kernel reconstruction for time-varying networks

AU - Ditzler, Gregory

AU - Bouaynaya, Nidhal

AU - Shterenberg, Roman

AU - Fathallah-Shaykh, Hassan M.

PY - 2019/2/6

Y1 - 2019/2/6

N2 - Background: Most existing algorithms for modeling and analyzing molecular networks assume a static or time-invariant network topology. Such view, however, does not render the temporal evolution of the underlying biological process as molecular networks are typically "re-wired" over time in response to cellular development and environmental changes. In our previous work, we formulated the inference of time-varying or dynamic networks as a tracking problem, where the target state is the ensemble of edges in the network. We used the Kalman filter to track the network topology over time. Unfortunately, the output of the Kalman filter does not reflect known properties of molecular networks, such as sparsity. Results: To address the problem of inferring sparse time-varying networks from a set of under-sampled measurements, we propose the Approximate Kernel RecONstruction (AKRON) Kalman filter. AKRON supersedes the Lasso regularization by starting from the Lasso-Kalman inferred network and judiciously searching the space for a sparser solution. We derive theoretical bounds for the optimality of AKRON. We evaluate our approach against the Lasso-Kalman filter on synthetic data. The results show that not only does AKRON-Kalman provide better reconstruction errors, but it is also better at identifying if edges exist within a network. Furthermore, we perform a real-world benchmark on the lifecycle (embryonic, larval, pupal, and adult stages) of the Drosophila Melanogaster. Conclusions: We show that the networks inferred by the AKRON-Kalman filter are sparse and can detect more known gene-to-gene interactions for the Drosophila melanogaster than the Lasso-Kalman filter. Finally, all of the code reported in this contribution will be publicly available.

AB - Background: Most existing algorithms for modeling and analyzing molecular networks assume a static or time-invariant network topology. Such view, however, does not render the temporal evolution of the underlying biological process as molecular networks are typically "re-wired" over time in response to cellular development and environmental changes. In our previous work, we formulated the inference of time-varying or dynamic networks as a tracking problem, where the target state is the ensemble of edges in the network. We used the Kalman filter to track the network topology over time. Unfortunately, the output of the Kalman filter does not reflect known properties of molecular networks, such as sparsity. Results: To address the problem of inferring sparse time-varying networks from a set of under-sampled measurements, we propose the Approximate Kernel RecONstruction (AKRON) Kalman filter. AKRON supersedes the Lasso regularization by starting from the Lasso-Kalman inferred network and judiciously searching the space for a sparser solution. We derive theoretical bounds for the optimality of AKRON. We evaluate our approach against the Lasso-Kalman filter on synthetic data. The results show that not only does AKRON-Kalman provide better reconstruction errors, but it is also better at identifying if edges exist within a network. Furthermore, we perform a real-world benchmark on the lifecycle (embryonic, larval, pupal, and adult stages) of the Drosophila Melanogaster. Conclusions: We show that the networks inferred by the AKRON-Kalman filter are sparse and can detect more known gene-to-gene interactions for the Drosophila melanogaster than the Lasso-Kalman filter. Finally, all of the code reported in this contribution will be publicly available.

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

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

U2 - 10.1186/s13040-019-0192-1

DO - 10.1186/s13040-019-0192-1

M3 - Article

AN - SCOPUS:85061151965

VL - 12

JO - BioData Mining

JF - BioData Mining

SN - 1756-0381

IS - 1

M1 - 5

ER -