Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Getting new algorithmic results by extending distance-hereditary graphs via split composition.

ABSTRACT: In this paper, we consider the graph class denoted as Gen(∗;P₃,C₃,C₅). It contains all graphs that can be generated by the split composition operation using path P₃, cycle C₃, and any cycle C₅ as components. This graph class extends the well-known class of distance-hereditary graphs, which corresponds, according to the adopted generative notation, to Gen(∗;P₃,C₃). We also use the concept of stretch number for providing a relationship between Gen(∗;P₃,C₃) and the hierarchy formed by the graph classes DH(k), with k ≥1, where DH(1) also coincides with the class of distance-hereditary graphs. For the addressed graph class, we prove there exist efficient algorithms for several basic combinatorial problems, like recognition, stretch number, stability number, clique number, domination number, chromatic number, and graph isomorphism. We also prove that graphs in the new class have bounded clique-width.

SUBMITTER: Cicerone S

PROVIDER: S-EPMC8279144 | biostudies-literature | 2021

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Getting new algorithmic results by extending distance-hereditary graphs via split composition.

Cicerone Serafino S Di Stefano Gabriele G

PeerJ. Computer science 20210707

In this paper, we consider the graph class denoted as Gen(∗;P3,C3,C5). It contains all graphs that can be generated by the split composition operation using path P3, cycle C3, and any cycle C5 as components. This graph class extends the well-known class of distance-hereditary graphs, which corresponds, according to the adopted generative notation, to Gen(∗;P3,C3). We also use the concept of stretch number for ...[more]

PMID: 34307866

Similar Datasets

An embedding-based distance for temporal graphs.

Project description:Temporal graphs are commonly used to represent time-resolved relations between entities in many natural and artificial systems. Many techniques were devised to investigate the evolution of temporal graphs by comparing their state at different time points. However, quantifying the similarity between temporal graphs as a whole is an open problem. Here, we use embeddings based on time-respecting random walks to introduce a new notion of distance between temporal graphs. This distance is well-defined for pairs of temporal graphs with different numbers of nodes and different time spans. We study the case of a matched pair of graphs, when a known relation exists between their nodes, and the case of unmatched graphs, when such a relation is unavailable and the graphs may be of different sizes. We use empirical and synthetic temporal network data to show that the distance we introduce discriminates graphs with different topological and temporal properties. We provide an efficient implementation of the distance computation suitable for large-scale temporal graphs.

| S-EPMC11570630 | biostudies-literature

Graphlet correlation distance to compare small graphs

Project description:Graph models are standard for representing mutual relationships between sets of entities. Often, graphs deal with a large number of entities with a small number of connections (e.g. social media relationships, infectious disease spread). The distances or similarities between such large graphs are known to be well established by the Graphlet Correlation Distance (GCD). This paper deals with small graphs (with potentially high densities of connections) that have been somewhat neglected in the literature but that concern important fora like sociology, ecology and fisheries, to mention some examples. First, based on numerical experiments, we study the conditions under which Erdős-Rényi, Fitness Scale-Free, Watts-Strogatz small-world and geometric graphs can be distinguished by a specific GCD measure based on 11 orbits, the GCD11. This is done with respect to the density and the order (i.e. the number of nodes) of the graphs when comparing graphs with the same and different orders. Second, we develop a randomization statistical test based on the GCD11 to compare empirical graphs to the four possible null models used in this analysis and apply it to a fishing case study where graphs represent pairwise proximity between fishing vessels. The statistical test rules out independent pairing within the fleet studied which is a standard assumption in fisheries. It also illustrates the difficulty to identify similarities between real-world small graphs and graph models.

| S-EPMC9931116 | biostudies-literature

High diagnostic yield with algorithmic molecular approach on hereditary neuropathies.

Project description:ObjectiveCharcot-Marie-Tooth disease covers a group of inherited peripheral neuropathies. The aim of this study was to investigate the effect of targeted next-generation sequencing panels on the molecular diagnosis of Charcot-Marie-Tooth disease and its subtypes in routine clinical practice, and also to show the limitations and importance of next-generation sequencing in the diagnosis of Charcot-Marie-Tooth diseases.MethodsThis is a retrospective study. Three different molecular methods (multiplex ligation probe amplification, next-generation sequencing, and whole-exome sequencing) were used to detect the mutations related to Charcot-Marie-Tooth disease.ResultsIn total, 64 patients (33 males and 31 females) with suspected Charcot-Marie-Tooth disease were analyzed for molecular etiology. In all, 25 (39%) patients were diagnosed by multiplex ligation probe amplification. With an extra 11 patients with normal PMP22 multiplex ligation probe amplification results that were consulted to our laboratory for further genetic analysis, a total of 50 patients underwent next-generation sequencing for targeted gene panels associated with Charcot-Marie-Tooth disease. Notably, 18 (36%) patients had pathogenic/likely pathogenic variants. Whole-exome sequencing was performed on five patients with normal next-generation sequencing results; the diagnostic yield by whole-exome sequencing was 80% and it was higher in the childhood group.ConclusionThe molecular etiology in Charcot-Marie-Tooth disease patients can be determined according to pre-test evaluation, deciding the inheritance type with pedigree analysis, the clinical phenotype, and an algorithm for the genetic analysis. The presence of patients without a molecular diagnosis in all the literature suggests that there are new genes or mechanisms waiting to be discovered in the etiology of Charcot-Marie-Tooth disease.

| S-EPMC9983476 | biostudies-literature

Getting there: How commuting time and distance impact students' health.

Project description:This study investigates the impact on Thai students' health of commuting to school, both in terms of time and distance. The individual-level dataset used in this study is obtained from the National Statistical Office (NSO) and limited to students aged from 9 to 18 years old, with 25,461 respondents. While the data were collected in 2016, with mostly unchanged commuting behaviors of Thai students, our results can reflect current health impacts from school commutes. The data indicate that traffic in Bangkok causes students to commute longer to schools than in other provinces. The results from the ordered logistic regression consistently show that commuting time has stronger negative impacts on health than commuting distance does. In other provinces, our results show that long commuting time and distance negatively affect physical and mental health of students. The present study also indicates that investigating either commuting distance or commuting time could bias the results in some sequences.

| S-EPMC11623559 | biostudies-literature

Hierarchical semantic composition of biosimulation models using bond graphs.

Project description:Simulating complex biological and physiological systems and predicting their behaviours under different conditions remains challenging. Breaking systems into smaller and more manageable modules can address this challenge, assisting both model development and simulation. Nevertheless, existing computational models in biology and physiology are often not modular and therefore difficult to assemble into larger models. Even when this is possible, the resulting model may not be useful due to inconsistencies either with the laws of physics or the physiological behaviour of the system. Here, we propose a general methodology for composing models, combining the energy-based bond graph approach with semantics-based annotations. This approach improves model composition and ensures that a composite model is physically plausible. As an example, we demonstrate this approach to automated model composition using a model of human arterial circulation. The major benefit is that modellers can spend more time on understanding the behaviour of complex biological and physiological systems and less time wrangling with model composition.

| S-EPMC8148364 | biostudies-literature

[Hereditary deafness in Turkey. Initial results].

Project description:The authors describe a study in progress to identify Turkish families with hereditary hearing loss and isolate possible responsible disease genes. Due to extreme genetic heterogeneity and limited audiological differentiation of hereditary hearing loss, it is necessary to identify large or small families from genetic isolates to locate loci responsible for hearing loss on a chromosome. To accomplish this goal, the medical records of 3800 children were examined at the ENT Clinic of Ege University between 1975 and 1994. All were suspected of having various hearing impairments. Additionally, students from two schools for the hearing impaired in Izmir and Eskisehir, Turkey were examined. To date, 16 families with syndromal deafness and 55 families with non-syndromal hereditary hearing loss involving two or more affected individuals have been identified and categorized according to the mode of inheritance. The majority (66%) of the non-syndromal families showed an autosomal recessive pattern, 29% an autosomal dominant inheritance and 5% an X-linked mode of inheritance. In the study presented there has been a predominance of affected males versus females and the consanguinity rate was 22%.

| S-EPMC6181136 | biostudies-other

Improving metagenomic binning results with overlapped bins using assembly graphs.

Project description:BackgroundMetagenomic sequencing allows us to study the structure, diversity and ecology in microbial communities without the necessity of obtaining pure cultures. In many metagenomics studies, the reads obtained from metagenomics sequencing are first assembled into longer contigs and these contigs are then binned into clusters of contigs where contigs in a cluster are expected to come from the same species. As different species may share common sequences in their genomes, one assembled contig may belong to multiple species. However, existing tools for binning contigs only support non-overlapped binning, i.e., each contig is assigned to at most one bin (species).ResultsIn this paper, we introduce GraphBin2 which refines the binning results obtained from existing tools and, more importantly, is able to assign contigs to multiple bins. GraphBin2 uses the connectivity and coverage information from assembly graphs to adjust existing binning results on contigs and to infer contigs shared by multiple species. Experimental results on both simulated and real datasets demonstrate that GraphBin2 not only improves binning results of existing tools but also supports to assign contigs to multiple bins.ConclusionGraphBin2 incorporates the coverage information into the assembly graph to refine the binning results obtained from existing binning tools. GraphBin2 also enables the detection of contigs that may belong to multiple species. We show that GraphBin2 outperforms its predecessor GraphBin on both simulated and real datasets. GraphBin2 is freely available at https://github.com/Vini2/GraphBin2 .

| S-EPMC8097841 | biostudies-literature

Extending the Propagation Distance of a Silver Nanowire Plasmonic Waveguide with a Dielectric Multilayer Substrate.

Project description:Chemical-synthesized silver nanowires have been proven as an efficient architecture for plasmonic waveguides, but the high propagation loss prevents their widely applications. Here, we demonstrate that the propagation distance of the plasmons along a silver nanowire can be extended if this nanowire was placed on a dielectric multilayer substrate containing a photonic band gap but not placed on a commonly used glass substrate. The propagation distance at 630 nm wavelength can reach 16 μm, even when the silver nanowire is as thin as 90 nm in diameter. Experimental and simulation results further show that the polarization of this propagating plasmon mode was nearly parallel to the surface of the dielectric multilayer, so it can be excited by a transverse-electric polarized Bloch surface wave propagating along a polymer nanowire with diameter at only about 170 nm on the same dielectric multilayer. Numerical simulations were also carried out and are consistent with the experiment results. Our work provides a platform with which to extend the propagation distance of the plasmonic waveguide and also for the integration between photonic and plasmonic waveguides on the nanometer scale.

| S-EPMC5814343 | biostudies-literature

Formulation Graphs for Mapping Structure-Composition of Battery Electrolytes to Device Performance.

Project description:Advanced computational methods are being actively sought to address the challenges associated with the discovery and development of new combinatorial materials, such as formulations. A widely adopted approach involves domain-informed high-throughput screening of individual components that can be combined together to form a formulation. This manages to accelerate the discovery of new compounds for a target application but still leaves the process of identifying the right "formulation" from the shortlisted chemical space largely a laboratory experiment-driven process. We report a deep learning model, the Formulation Graph Convolution Network (F-GCN), that can map the structure-composition relationship of the formulation constituents to the property of liquid formulation as a whole. Multiple GCNs are assembled in parallel that featurize formulation constituents domain-intuitively on the fly. The resulting molecular descriptors are scaled based on the respective constituent's molar percentage in the formulation, followed by integration into a combined formulation descriptor that represents the complete formulation to an external learning architecture. The use case of the proposed formulation learning model is demonstrated for battery electrolytes by training and testing it on two exemplary data sets representing electrolyte formulations vs battery performance: one data set is sourced from the literature about Li/Cu half-cells, while the other is obtained by lab experiments related to lithium-iodide full-cell chemistry. The model is shown to predict performance metrics such as Coulombic efficiency (CE) and specific capacity of new electrolyte formulations with the lowest reported errors. The best-performing F-GCN model uses molecular descriptors derived from molecular graphs (GCNs) that are informed with HOMO-LUMO and electric moment properties of the molecules using a knowledge transfer technique.

| S-EPMC10685446 | biostudies-literature

Exploiting the detector distance information in image scanning microscopy by phasor-based SPLIT-ISM.

Project description:Confocal microscopy is an important bio-imaging technique that increases the resolution using a spatial pinhole to block out-of-focus light. In theory, the maximum resolution and optical sectioning are obtained when the detection pinhole is fully closed, but this is prevented by the dramatic decrease in the signal reaching the detector. In image scanning microscopy (ISM) this limitation is overcome by the use of an array of point detectors rather than a single detector. This, combined with pixel reassignment, increases the resolution of 2 over widefield imaging, with relatively little modification to the existing hardware of a laser-scanning microscope. Separation of photons by lifetime tuning (SPLIT) is a super-resolution technique, based on the phasor analysis of the fluorescent signal into an additional channel of the microscope. Here, we use SPLIT to analyze the information encoded within the array detectors distance for improving the resolution of ISM (SPLIT-ISM). We find that the lateral resolution can be increased of an additional 1.3 × with respect to the pixel-reassigned image with a concomitant increase in optical sectioning. We applied the SPLIT-ISM technique on biological images acquired by two currently available ISM systems: the Genoa Instruments PRISM and the Zeiss Airyscan. We evaluate the improvement provided by SPLIT-ISM through the QuICS algorithm, a quantitative tool based on image correlation spectroscopy. QuICS allows extracting three parameters related to the resolution, and contrast SNR of the image. We find that SPLIT-ISM provides an increase in spatial resolution for both the Genoa Instrument PRISM and the Zeiss Airyscan microscopes.

| S-EPMC11919353 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data