Limits...
Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Bottom Line: We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph.We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex.This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.

View Article: PubMed Central - PubMed

Affiliation: Center for Studies in Physics and Biology, The Rockefeller University, New York, New York, United States of America. ekatifori@rockefeller.edu

ABSTRACT
Biology presents many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture containing closed loops at many different levels. Although a number of approaches have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex. We calculate various metrics based on the asymmetry, the cumulative size distribution and the Strahler bifurcation ratios of the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.

Show MeSH

Related in: MedlinePlus

Hierarchical decomposition and segmentation of two dicotyledonous leaves.(a) Segments of digitized leaf vasculature. The image of the skeletonized leaf has been overlayed with the digitized portion of interest. (a1) Bursera tecomaca, (a2) Protium heptaphyllum. Images courtesy of Douglas Daly, New York Botanical Gardens. (b) Hierarchical decomposition of Bursera and Protium. (b1) Bursera, (b2) Protium. Top to bottom: remaining loops at three different, progressively higher thickness cutoffs. Notice the persistent minor loops at the proximity of the major veins. (c) Segmentation of Protium heptaphyllum and associated tree representation. The protium intercostal area area has been separated to six color-coded sectors, as identified by hierarchical decomposition. The associated tree representation for that sector is shown for the green and red sector. The non-colored (white) areas of the graph and associated gray links on the tree representation correspond to high asymmetry nodes of the tree representation. Note how the high asymmetry areas are concentrated near major leaf veins.
© Copyright Policy
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g008: Hierarchical decomposition and segmentation of two dicotyledonous leaves.(a) Segments of digitized leaf vasculature. The image of the skeletonized leaf has been overlayed with the digitized portion of interest. (a1) Bursera tecomaca, (a2) Protium heptaphyllum. Images courtesy of Douglas Daly, New York Botanical Gardens. (b) Hierarchical decomposition of Bursera and Protium. (b1) Bursera, (b2) Protium. Top to bottom: remaining loops at three different, progressively higher thickness cutoffs. Notice the persistent minor loops at the proximity of the major veins. (c) Segmentation of Protium heptaphyllum and associated tree representation. The protium intercostal area area has been separated to six color-coded sectors, as identified by hierarchical decomposition. The associated tree representation for that sector is shown for the green and red sector. The non-colored (white) areas of the graph and associated gray links on the tree representation correspond to high asymmetry nodes of the tree representation. Note how the high asymmetry areas are concentrated near major leaf veins.

Mentions: In this section we apply the hierarchical decomposition for two real examples, a leaf from Bursera tecomaca and a leaf from Protium heptaphyllum, show on Fig.8. The leaves have been cleared and stained by the group of D. Daly in the New York Botanical Gardens, who provided us with high resolution images of the specimens. We reconstructed and digitized the vasculature of leaves using custom made software that we have developed to translate the pixel values information to a collection of nodes and edges on which we can perform hierarchical decomposition.


Quantifying loopy network architectures.

Katifori E, Magnasco MO - PLoS ONE (2012)

Hierarchical decomposition and segmentation of two dicotyledonous leaves.(a) Segments of digitized leaf vasculature. The image of the skeletonized leaf has been overlayed with the digitized portion of interest. (a1) Bursera tecomaca, (a2) Protium heptaphyllum. Images courtesy of Douglas Daly, New York Botanical Gardens. (b) Hierarchical decomposition of Bursera and Protium. (b1) Bursera, (b2) Protium. Top to bottom: remaining loops at three different, progressively higher thickness cutoffs. Notice the persistent minor loops at the proximity of the major veins. (c) Segmentation of Protium heptaphyllum and associated tree representation. The protium intercostal area area has been separated to six color-coded sectors, as identified by hierarchical decomposition. The associated tree representation for that sector is shown for the green and red sector. The non-colored (white) areas of the graph and associated gray links on the tree representation correspond to high asymmetry nodes of the tree representation. Note how the high asymmetry areas are concentrated near major leaf veins.
© Copyright Policy
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3368948&req=5

pone-0037994-g008: Hierarchical decomposition and segmentation of two dicotyledonous leaves.(a) Segments of digitized leaf vasculature. The image of the skeletonized leaf has been overlayed with the digitized portion of interest. (a1) Bursera tecomaca, (a2) Protium heptaphyllum. Images courtesy of Douglas Daly, New York Botanical Gardens. (b) Hierarchical decomposition of Bursera and Protium. (b1) Bursera, (b2) Protium. Top to bottom: remaining loops at three different, progressively higher thickness cutoffs. Notice the persistent minor loops at the proximity of the major veins. (c) Segmentation of Protium heptaphyllum and associated tree representation. The protium intercostal area area has been separated to six color-coded sectors, as identified by hierarchical decomposition. The associated tree representation for that sector is shown for the green and red sector. The non-colored (white) areas of the graph and associated gray links on the tree representation correspond to high asymmetry nodes of the tree representation. Note how the high asymmetry areas are concentrated near major leaf veins.
Mentions: In this section we apply the hierarchical decomposition for two real examples, a leaf from Bursera tecomaca and a leaf from Protium heptaphyllum, show on Fig.8. The leaves have been cleared and stained by the group of D. Daly in the New York Botanical Gardens, who provided us with high resolution images of the specimens. We reconstructed and digitized the vasculature of leaves using custom made software that we have developed to translate the pixel values information to a collection of nodes and edges on which we can perform hierarchical decomposition.

Bottom Line: We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph.We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex.This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.

View Article: PubMed Central - PubMed

Affiliation: Center for Studies in Physics and Biology, The Rockefeller University, New York, New York, United States of America. ekatifori@rockefeller.edu

ABSTRACT
Biology presents many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture containing closed loops at many different levels. Although a number of approaches have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex. We calculate various metrics based on the asymmetry, the cumulative size distribution and the Strahler bifurcation ratios of the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs.

Show MeSH
Related in: MedlinePlus