Fuzzy Connectedness Image Segmentation in Graph Cut Formulation: A Linear-Time Algorithm and a Comparative Analysis

A deep theoretical analysis of the graph cut image segmentation framework presented in this paper simultaneously translates into important contributions in several directions. The most important practical contribution of this work is a full theoretical description, and implementation, of a novel powerful segmentation algorithm, GC(max). The output of GC(max) coincides with a version of a segmentation algorithm known as Iterative Relative Fuzzy Connectedness, IRFC. However, GC(max) is considerably faster than the classic IRFC algorithm, which we prove theoretically and show experimentally. Specifically, we prove that, in the worst case scenario, the GC(max) algorithm runs in linear time with respect to the variable M=|C|+|Z|, where |C| is the image scene size and |Z| is the size of the allowable range, Z, of the associated weight/affinity function. For most implementations, Z is identical to the set of allowable image intensity values, and its size can be treated as small with respect to |C|, meaning that O(M)=O(|C|). In such a situation, GC(max) runs in linear time with respect to the image size |C|. We show that the output of GC(max) constitutes a solution of a graph cut energy minimization problem, in which the energy is defined as the a"" (a) norm ayenF (P) ayen(a) of the map F (P) that associates, with every element e from the boundary of an object P, its weight w(e). This formulation brings IRFC algorithms to the realm of the graph cut energy minimizers, with energy functions ayenF (P) ayen (q) for qa[1,a]. Of these, the best known minimization problem is for the energy ayenF (P) ayen(1), which is solved by the classic min-cut/max-flow algorithm, referred to often as the Graph Cut algorithm. We notice that a minimization problem for ayenF (P) ayen (q) , qa[1,a), is identical to that for ayenF (P) ayen(1), when the original weight function w is replaced by w (q) . Thus, any algorithm GC(sum) solving the ayenF (P) ayen(1) minimization problem, solves also one for ayenF (P) ayen (q) with qa[1,a), so just two algorithms, GC(sum) and GC(max), are enough to solve all ayenF (P) ayen (q) -minimization problems. We also show that, for any fixed weight assignment, the solutions of the ayenF (P) ayen (q) -minimization problems converge to a solution of the ayenF (P) ayen(a)-minimization problem (ayenF (P) ayen(a)=lim (q -> a)ayenF (P) ayen (q) is not enough to deduce that). An experimental comparison of the performance of GC(max) and GC(sum) algorithms is included. This concentrates on comparing the actual (as opposed to provable worst scenario) algorithms' running time, as well as the influence of the choice of the seeds on the output.

Partitioning and extraction of collagenase from Penicillium aurantiogriseum in poly(ethylene glycol)/phosphate aqueous two-phase system

Purification of collagenase produced by Penicillium aurantiogriseum URM4622 was carried using a PEG/phosphate aqueous two-phase system (ATPS). A 2(3)-full experimental design was used to investigate the influence of PEG molar mass, PEG concentration and phosphate concentration on the selected responses, namely partition coefficient, activity yield and purification factor. The ATPS was composed of PEG (molar mass of 550, 1500 and 4000 g/mol) at concentrations of 15.0, 17.5 and 20.0% (w/w) and phosphate at concentrations of 12.5, 15.0 and 17.5% (w/w). The best results of one-step extraction of collagenase from the fermentation broth (partition coefficient of 1.01, activity yield of 242% and purification factor of 23.5) were obtained at pH 6.0 using 20.0% (w/w) PEG 550 and 17.5% (w/w) phosphate. The results of this preliminary study demonstrate that the selected ATPS is satisfactorily selective for the extraction of such a collagenase. (C) 2012 Elsevier B.V. All rights reserved.

Algebraic-graph method for identification of islanding in power system grids

In this paper, a new algebraic-graph method for identification of islanding in power system grids is proposed. The proposed method identifies all the possible cases of islanding, due to the loss of a equipment, by means of a factorization of the bus-branch incidence matrix. The main features of this new method include: (i) simple implementation, (ii) high speed, (iii) real-time adaptability, (iv) identification of all islanding cases and (v) identification of the buses that compose each island in case of island formation. The method was successfully tested on large-scale systems such as the reduced south Brazilian system (45 buses/72 branches) and the south-southeast Brazilian system (810 buses/1340 branches). (C) 2011 Elsevier Ltd. All rights reserved.

Stand-level patterns of carbon fluxes and partitioning in a Eucalyptus grandis plantation across a gradient of productivity, in Sao Paulo State, Brazil

Wood production represents a large but variable fraction of gross primary production (GPP) in highly productive Eucalyptus plantations. Assessing patterns of carbon (C) partitioning (C flux as a fraction of GPP) between above- and belowground components is essential to understand mechanisms driving the C budget of these plantations. Better knowledge of fluxes and partitioning to woody and non-woody tissues in response to site characteristics and resource availability could provide opportunities to increase forest productivity. Our study aimed at investigating how C allocation varied within one apparently homogeneous 90 ha stand of Eucalyptus grandis (W. Hill ex Maiden) in Southeastern Brazil. We assessed annual above-ground net primary production (ANPP: stem, leaf, and branch production) and total belowground C flux (TBCF: the sum of root production and respiration and mycorrhizal production and respiration), GPP (computed as the sum of ANPP, TBCF and estimated aboveground respiration) on 12 plots representing the gradient of productivity found within the stand. The spatial heterogeneity of topography and associated soil attributes across the stand likely explained this fertility gradient. Component fluxes of GPP and C partitioning were found to vary among plots. Stem NPP ranged from 554 g C m(-2) year(-1) on the plot with lowest GPP to 923 g C m(-2) year(-1) on the plot with highest GPP. Total belowground carbon flux ranged from 497 to 1235 g C m(-2) year(-1) and showed no relationship with ANPP or GPP. Carbon partitioning to stem NPP increased from 0.19 to 0.23, showing a positive trend of increase with GPP (R-2 = 0.29, P = 0.07). Variations in stem wood production across the gradient of productivity observed at our experimental site were a result of the variability in C partitioning to different forest system components.

Brazilian sardine (Sardinella brasiliensis Steindachner, 1879) spawning and nursery habitats: spatial-scale partitioning and multiscale relationships with thermohaline descriptors

We provide a detailed account of the spatial structure of the Brazilian sardine (Sardinella brasiliensis) spawning and nursery habitats, using ichthyoplankton data from nine surveys (1976-1993) covering the Southeastern Brazilian Bight (SBB). The spatial variability of sardine eggs and larvae was partitioned into predefined spatial-scale classes (broad scale, 200-500 km; medium scale, 50-100 km; and local scale, <50 km). The relationship between density distributions at both developmental stages and environmental descriptors (temperature and salinity) was also explored within these spatial scales. Spatial distributions of sardine eggs were mostly structured on medium and local scales, while larvae were characterized by broad-and medium-scale distributions. Broad-and medium-scale surface temperatures were positively correlated with sardine densities, for both developmental stages. Correlations with salinity were predominantly negative and concentrated on a medium scale. Broad-scale structuring might be explained by mesoscale processes, such as pulsing upwelling events and Brazil Current meandering at the northern portion of the SBB, while medium-scale relationships may be associated with local estuarine outflows. The results indicate that processes favouring vertical stability might regulate the spatial extensions of suitable spawning and nursery habitats for the Brazilian sardine.

Is shell partitioning between the hermit crabs Pagurus brevidactylus and Pagurus criniticornis explained by interference and/or exploitation competition?

The effect of crab behaviour on shell-use dynamics was analysed, comparing both interference and exploitation behaviours between the hermit crabs Pagurus criniticornis and Pagurus brevidactylus. Although these species exhibited microhabitat separation, with P. criniticornis dominating (100%) in sandy substrates and P. brevidactylus (80%) on rocky shores, they overlapped in the rocky shore/sand interface (P. criniticornis, 53%; P. brevidactylus, 43%). Pagurus criniticornis occupied shells of Cerithium atratum in higher frequencies (84%) than P. brevidactylus (37%), which was hypothesized to be a consequence of competitive interactions combined with their ability to acquire and/or retain this resource. The species P. criniticornis was attracted in larger numbers to simulated gastropod predation events than was P. brevidactylus, which, on the few occasions that it moved before P. criniticornis, tended to be attracted more rapidly. Interspecific shell exchanges between these species were few, suggesting the absence of dominance relationships. The shell-use pattern in this species pair is thus defined by exploitation competition, which is presumed to be intensified in areas of microsympatry. These results differ from other studies, which found that interference competition through interspecific exchanges shapes shell use, indicating that shell partitioning in hermit crabs is dependent on the behaviour of the species involved in the contests.

Soil carbon balance in a tropical grassland: Estimation of soil respiration and its partitioning using a semi-empirical model

In savannah and tropical grasslands, which account for 60% of grasslands worldwide, a large share of ecosystem carbon is located below ground due to high root:shoot ratios. Temporal variations in soil CO2 efflux (R-S) were investigated in a grassland of coastal Congo over two years. The objectives were (1) to identify the main factors controlling seasonal variations in R-S and (2) to develop a semi-empirical model describing R-S and including a heterotrophic component (R-H) and an autotrophic component (R-A). Plant above-ground activity was found to exert strong control over soil respiration since 71% of seasonal R-S variability was explained by the quantity of photosynthetically active radiation absorbed (APAR) by the grass canopy. We tested an additive model including a parameter enabling R-S partitioning into R-A and R-H. Assumptions underlying this model were that R-A mainly depended on the amount of photosynthates allocated below ground and that microbial and root activity was mostly controlled by soil temperature and soil moisture. The model provided a reasonably good prediction of seasonal variations in R-S (R-2 = 0.85) which varied between 5.4 mu mol m(-2) s(-1) in the wet season and 0.9 mu mol m(-2) s(-1) at the end of the dry season. The model was subsequently used to obtain annual estimates of R-S, R-A and R-H. In accordance with results reported for other tropical grasslands, we estimated that R-H accounted for 44% of R-S, which represented a flux similar to the amount of carbon brought annually to the soil from below-ground litter production. Overall, this study opens up prospects for simulating the carbon budget of tropical grasslands on a large scale using remotely sensed data. (C) 2012 Elsevier B.V. All rights reserved.

A graph-theoretical approach in brain functional networks. Possible implications in EEG studies

Abstract Background Recently, it was realized that the functional connectivity networks estimated from actual brain-imaging technologies (MEG, fMRI and EEG) can be analyzed by means of the graph theory, that is a mathematical representation of a network, which is essentially reduced to nodes and connections between them. Methods We used high-resolution EEG technology to enhance the poor spatial information of the EEG activity on the scalp and it gives a measure of the electrical activity on the cortical surface. Afterwards, we used the Directed Transfer Function (DTF) that is a multivariate spectral measure for the estimation of the directional influences between any given pair of channels in a multivariate dataset. Finally, a graph theoretical approach was used to model the brain networks as graphs. These methods were used to analyze the structure of cortical connectivity during the attempt to move a paralyzed limb in a group (N=5) of spinal cord injured patients and during the movement execution in a group (N=5) of healthy subjects. Results Analysis performed on the cortical networks estimated from the group of normal and SCI patients revealed that both groups present few nodes with a high out-degree value (i.e. outgoing links). This property is valid in the networks estimated for all the frequency bands investigated. In particular, cingulate motor areas (CMAs) ROIs act as ‘‘hubs’’ for the outflow of information in both groups, SCI and healthy. Results also suggest that spinal cord injuries affect the functional architecture of the cortical network sub-serving the volition of motor acts mainly in its local feature property. In particular, a higher local efficiency El can be observed in the SCI patients for three frequency bands, theta (3-6 Hz), alpha (7-12 Hz) and beta (13-29 Hz). By taking into account all the possible pathways between different ROI couples, we were able to separate clearly the network properties of the SCI group from the CTRL group. In particular, we report a sort of compensatory mechanism in the SCI patients for the Theta (3-6 Hz) frequency band, indicating a higher level of “activation” Ω within the cortical network during the motor task. The activation index is directly related to diffusion, a type of dynamics that underlies several biological systems including possible spreading of neuronal activation across several cortical regions. Conclusions The present study aims at demonstrating the possible applications of graph theoretical approaches in the analyses of brain functional connectivity from EEG signals. In particular, the methodological aspects of the i) cortical activity from scalp EEG signals, ii) functional connectivity estimations iii) graph theoretical indexes are emphasized in the present paper to show their impact in a real application.

Labeling the nodes in the intrinsic order graph with their weights

[EN] This paper deals with the study of some new properties of the intrinsic order graph. The intrinsic order graph is the natural graphical representation of a complex stochastic Boolean system (CSBS). A CSBS is a system depending on an arbitrarily large number n of mutually independent random Boolean variables. The intrinsic order graph displays its 2n vertices (associated to the CSBS) from top to bottom, in decreasing order of their occurrence probabilities. New relations between the intrinsic ordering and the Hamming weight (i.e., the number of 1-bits in a binary n-tuple) are derived. Further, the distribution of the weights of the 2n nodes in the intrinsic order graph is analyzed…

Complex sochastic boolean systems : new properties of the intrinsic order graph

[EN]A complex stochastic Boolean system (CSBS) is a system depending on an arbitrary number n of stochastic Boolean variables. The analysis of CSBSs is mainly based on the intrinsic order: a partial order relation defined on the set f0; 1gn of binary n-tuples. The usual graphical representation for a CSBS is the intrinsic order graph: the Hasse diagram of the intrinsic order. In this paper, some new properties of the intrinsic order graph are studied. Particularly, the set and the number of its edges, the degree and neighbors of each vertex, as well as typical properties, such as the symmetry and fractal structure of this graph, are analyzed…

Exact computation of the adjacency graph of an arrangement of quadrics

Präsentiert wird ein vollständiger, exakter und effizienter Algorithmus zur Berechnung des Nachbarschaftsgraphen eines Arrangements von Quadriken (Algebraische Flächen vom Grad 2). Dies ist ein wichtiger Schritt auf dem Weg zur Berechnung des vollen 3D Arrangements. Dabei greifen wir auf eine bereits existierende Implementierung zur Berechnung der exakten Parametrisierung der Schnittkurve von zwei Quadriken zurück. Somit ist es möglich, die exakten Parameterwerte der Schnittpunkte zu bestimmen, diese entlang der Kurven zu sortieren und den Nachbarschaftsgraphen zu berechnen. Wir bezeichnen unsere Implementierung als vollständig, da sie auch die Behandlung aller Sonderfälle wie singulärer oder tangentialer Schnittpunkte einschließt. Sie ist exakt, da immer das mathematisch korrekte Ergebnis berechnet wird. Und schließlich bezeichnen wir unsere Implementierung als effizient, da sie im Vergleich mit dem einzigen bisher implementierten Ansatz gut abschneidet. Implementiert wurde unser Ansatz im Rahmen des Projektes EXACUS. Das zentrale Ziel von EXACUS ist es, einen Prototypen eines zuverlässigen und leistungsfähigen CAD Geometriekerns zu entwickeln. Obwohl wir das Design unserer Bibliothek als prototypisch bezeichnen, legen wir dennoch größten Wert auf Vollständigkeit, Exaktheit, Effizienz, Dokumentation und Wiederverwendbarkeit. Über den eigentlich Beitrag zu EXACUS hinaus, hatte der hier vorgestellte Ansatz durch seine besonderen Anforderungen auch wesentlichen Einfluss auf grundlegende Teile von EXACUS. Im Besonderen hat diese Arbeit zur generischen Unterstützung der Zahlentypen und der Verwendung modularer Methoden innerhalb von EXACUS beigetragen. Im Rahmen der derzeitigen Integration von EXACUS in CGAL wurden diese Teile bereits erfolgreich in ausgereifte CGAL Pakete weiterentwickelt.

Geological and hydrogeological features affecting migration, multi-phase partitioning and degradation of chlorinated hydrocarbons through unconsolidated porous media.

Chlorinated solvents are the most ubiquitous organic contaminants found in groundwater since the last five decades. They generally reach groundwater as Dense Non-Aqueous Phase Liquid (DNAPL). This phase can migrate through aquifers, and also through aquitards, in ways that aqueous contaminants cannot. The complex phase partitioning to which chlorinated solvent DNAPLs can undergo (i.e. to the dissolved, vapor or sorbed phase), as well as their transformations (e.g. degradation), depend on the physico-chemical properties of the contaminants themselves and on features of the hydrogeological system. The main goal of the thesis is to provide new knowledge for the future investigations of sites contaminated by DNAPLs in alluvial settings, proposing innovative investigative approaches and emphasizing some of the key issues and main criticalities of this kind of contaminants in such a setting. To achieve this goal, the hydrogeologic setting below the city of Ferrara (Po plain, northern Italy), which is affected by scattered contamination by chlorinated solvents, has been investigated at different scales (regional and site specific), both from an intrinsic (i.e. groundwater flow systems) and specific (i.e. chlorinated solvent DNAPL behavior) point of view. Detailed investigations were carried out in particular in one selected test-site, known as “Caretti site”, where high-resolution vertical profiling of different kind of data were collected by means of multilevel monitoring systems and other innovative sampling and analytical techniques. This allowed to achieve a deep geological and hydrogeological knowledge of the system and to reconstruct in detail the architecture of contaminants in relationship to the features of the hosting porous medium. The results achieved in this thesis are useful not only at local scale, e.g. employable to interpret the origin of contamination in other sites of the Ferrara area, but also at global scale, in order to address future remediation and protection actions of similar hydrogeologic settings.

Graph algorithms for bioinformatics

Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, thanks to constraints on the data and dynamic programming. The proposed algorithm ideally improves the generation time by a factor of 5. The graph representation is then exploited to build a comprehensive database, thanks to the rising technology of graph databases. While graph databases are widely used for other kind of data, from Twitter tweets to recommendation systems, their application to bioinformatics is new. A graph database is proposed, with a structure that can be easily expanded and queried.

Graph-based analysis of brain resting-state fMRI data in nocturnal frontal lobe epileptic patients

Il lavoro che ho sviluppato presso l'unità di RM funzionale del Policlinico S.Orsola-Malpighi, DIBINEM, è incentrato sull'analisi dati di resting state - functional Magnetic Resonance Imaging (rs-fMRI) mediante l'utilizzo della graph theory, con lo scopo di valutare eventuali differenze in termini di connettività cerebrale funzionale tra un campione di pazienti affetti da Nocturnal Frontal Lobe Epilepsy (NFLE) ed uno di controlli sani. L'epilessia frontale notturna è una peculiare forma di epilessia caratterizzata da crisi che si verificano quasi esclusivamente durante il sonno notturno. Queste sono contraddistinte da comportamenti motori, prevalentemente distonici, spesso complessi, e talora a semiologia bizzarra. L'fMRI è una metodica di neuroimaging avanzata che permette di misurare indirettamente l'attività neuronale. Tutti i soggetti sono stati studiati in condizioni di resting-state, ossia di veglia rilassata. In particolare mi sono occupato di analizzare i dati fMRI con un approccio innovativo in campo clinico-neurologico, rappresentato dalla graph theory. I grafi sono definiti come strutture matematiche costituite da nodi e links, che trovano applicazione in molti campi di studio per la modellizzazione di strutture di diverso tipo. La costruzione di un grafo cerebrale per ogni partecipante allo studio ha rappresentato la parte centrale di questo lavoro. L'obiettivo è stato quello di definire le connessioni funzionali tra le diverse aree del cervello mediante l'utilizzo di un network. Il processo di modellizzazione ha permesso di valutare i grafi neurali mediante il calcolo di parametri topologici che ne caratterizzano struttura ed organizzazione. Le misure calcolate in questa analisi preliminare non hanno evidenziato differenze nelle proprietà globali tra i grafi dei pazienti e quelli dei controlli. Alterazioni locali sono state invece riscontrate nei pazienti, rispetto ai controlli, in aree della sostanza grigia profonda, del sistema limbico e delle regioni frontali, le quali rientrano tra quelle ipotizzate essere coinvolte nella fisiopatologia di questa peculiare forma di epilessia.