Cargando…
Critical controllability analysis of directed biological networks using efficient graph reduction
Network science has recently integrated key concepts from control theory and has applied them to the analysis of the controllability of complex networks. One of the proposed frameworks uses the Minimum Dominating Set (MDS) approach, which has been successfully applied to the identification of cancer...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Nature Publishing Group UK
2017
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5662738/ https://www.ncbi.nlm.nih.gov/pubmed/29084972 http://dx.doi.org/10.1038/s41598-017-14334-8 |
_version_ | 1783274694553632768 |
---|---|
author | Ishitsuka, Masayuki Akutsu, Tatsuya Nacher, Jose C. |
author_facet | Ishitsuka, Masayuki Akutsu, Tatsuya Nacher, Jose C. |
author_sort | Ishitsuka, Masayuki |
collection | PubMed |
description | Network science has recently integrated key concepts from control theory and has applied them to the analysis of the controllability of complex networks. One of the proposed frameworks uses the Minimum Dominating Set (MDS) approach, which has been successfully applied to the identification of cancer-related proteins and in analyses of large-scale undirected networks, such as proteome-wide protein interaction networks. However, many real systems are better represented by directed networks. Therefore, fast algorithms are required for the application of MDS to directed networks. Here, we propose an algorithm that utilises efficient graph reduction to identify critical control nodes in large-scale directed complex networks. The algorithm is 176-fold faster than existing methods and increases the computable network size to 65,000 nodes. We then applied the developed algorithm to metabolic pathways consisting of 70 plant species encompassing major plant lineages ranging from algae to angiosperms and to signalling pathways from C. elegans, D. melanogaster and H. sapiens. The analysis not only identified functional pathways enriched with critical control molecules but also showed that most control categories are largely conserved across evolutionary time, from green algae and early basal plants to modern angiosperm plant lineages. |
format | Online Article Text |
id | pubmed-5662738 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2017 |
publisher | Nature Publishing Group UK |
record_format | MEDLINE/PubMed |
spelling | pubmed-56627382017-11-08 Critical controllability analysis of directed biological networks using efficient graph reduction Ishitsuka, Masayuki Akutsu, Tatsuya Nacher, Jose C. Sci Rep Article Network science has recently integrated key concepts from control theory and has applied them to the analysis of the controllability of complex networks. One of the proposed frameworks uses the Minimum Dominating Set (MDS) approach, which has been successfully applied to the identification of cancer-related proteins and in analyses of large-scale undirected networks, such as proteome-wide protein interaction networks. However, many real systems are better represented by directed networks. Therefore, fast algorithms are required for the application of MDS to directed networks. Here, we propose an algorithm that utilises efficient graph reduction to identify critical control nodes in large-scale directed complex networks. The algorithm is 176-fold faster than existing methods and increases the computable network size to 65,000 nodes. We then applied the developed algorithm to metabolic pathways consisting of 70 plant species encompassing major plant lineages ranging from algae to angiosperms and to signalling pathways from C. elegans, D. melanogaster and H. sapiens. The analysis not only identified functional pathways enriched with critical control molecules but also showed that most control categories are largely conserved across evolutionary time, from green algae and early basal plants to modern angiosperm plant lineages. Nature Publishing Group UK 2017-10-30 /pmc/articles/PMC5662738/ /pubmed/29084972 http://dx.doi.org/10.1038/s41598-017-14334-8 Text en © The Author(s) 2017 Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/. |
spellingShingle | Article Ishitsuka, Masayuki Akutsu, Tatsuya Nacher, Jose C. Critical controllability analysis of directed biological networks using efficient graph reduction |
title | Critical controllability analysis of directed biological networks using efficient graph reduction |
title_full | Critical controllability analysis of directed biological networks using efficient graph reduction |
title_fullStr | Critical controllability analysis of directed biological networks using efficient graph reduction |
title_full_unstemmed | Critical controllability analysis of directed biological networks using efficient graph reduction |
title_short | Critical controllability analysis of directed biological networks using efficient graph reduction |
title_sort | critical controllability analysis of directed biological networks using efficient graph reduction |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5662738/ https://www.ncbi.nlm.nih.gov/pubmed/29084972 http://dx.doi.org/10.1038/s41598-017-14334-8 |
work_keys_str_mv | AT ishitsukamasayuki criticalcontrollabilityanalysisofdirectedbiologicalnetworksusingefficientgraphreduction AT akutsutatsuya criticalcontrollabilityanalysisofdirectedbiologicalnetworksusingefficientgraphreduction AT nacherjosec criticalcontrollabilityanalysisofdirectedbiologicalnetworksusingefficientgraphreduction |