Reordering hierarchical tree based on bilateral symmetric distance.
Ontology highlight
ABSTRACT: Background
In microarray data analysis, hierarchical clustering (HC) is often used to group samples or genes according to their gene expression profiles to study their associations. In a typical HC, nested clustering structures can be quickly identified in a tree. The relationship between objects is lost, however, because clusters rather than individual objects are compared. This results in a tree that is hard to interpret.Methodology/principal findings
This study proposes an ordering method, HC-SYM, which minimizes bilateral symmetric distance of two adjacent clusters in a tree so that similar objects in the clusters are located in the cluster boundaries. The performance of HC-SYM was evaluated by both supervised and unsupervised approaches and compared favourably with other ordering methods.Conclusions/significance
The intuitive relationship between objects and flexibility of the HC-SYM method can be very helpful in the exploratory analysis of not only microarray data but also similar high-dimensional data.
SUBMITTER: Chae M
PROVIDER: S-EPMC3150382 | biostudies-literature | 2011
REPOSITORIES: biostudies-literature
Publications
Reordering hierarchical tree based on bilateral symmetric distance.
PloS one 20110804 8
<h4>Background</h4>In microarray data analysis, hierarchical clustering (HC) is often used to group samples or genes according to their gene expression profiles to study their associations. In a typical HC, nested clustering structures can be quickly identified in a tree. The relationship between objects is lost, however, because clusters rather than individual objects are compared. This results in a tree that is hard to interpret.<h4>Methodology/principal findings</h4>This study proposes an ord ...[more]
Similar Datasets
Project description:Several popular methods for phylogenetic inference (or hierarchical clustering) are based on a matrix of pairwise distances between taxa (or any kind of objects): The objective is to construct a tree with branch lengths so that the distances between the leaves in that tree are as close as possible to the input distances. If we hold the structure (topology) of the tree fixed, in some relevant cases (e.g., ordinary least squares) the optimal values for the branch lengths can be expressed using simple combinatorial formulae. Here we define a general form for these formulae and show that they all have two desirable properties: First, the common tree reconstruction approaches (least squares, minimum evolution), when used in combination with these formulae, are guaranteed to infer the correct tree when given enough data (consistency); second, the branch lengths of all the simple (nearest neighbor interchange) rearrangements of a tree can be calculated, optimally, in quadratic time in the size of the tree, thus allowing the efficient application of hill climbing heuristics. The study presented here is a continuation of that by Mihaescu and Pachter on branch length estimation [Mihaescu R, Pachter L (2008) Proc Natl Acad Sci USA 105:13206-13211]. The focus here is on the inference of the tree itself and on providing a basis for novel algorithms to reconstruct trees from distances.
| S-EPMC3478627 | biostudies-literature
Project description:MotivationTracing of neuron morphology is an essential technique in computational neuroscience. However, despite a number of existing methods, few open-source techniques are completely or sufficiently automated and at the same time are able to generate robust results for real 3D microscopy images.ResultsWe developed all-path-pruning 2.0 (APP2) for 3D neuron tracing. The most important idea is to prune an initial reconstruction tree of a neuron's morphology using a long-segment-first hierarchical procedure instead of the original termini-first-search process in APP. To further enhance the robustness of APP2, we compute the distance transform of all image voxels directly for a gray-scale image, without the need to binarize the image before invoking the conventional distance transform. We also design a fast-marching algorithm-based method to compute the initial reconstruction trees without pre-computing a large graph. This method allows us to trace large images. We bench-tested APP2 on ~700 3D microscopic images and found that APP2 can generate more satisfactory results in most cases than several previous methods.AvailabilityThe software has been implemented as an open-source Vaa3D plugin. The source code is available in the Vaa3D code repository http://vaa3d.org.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC3661058 | biostudies-literature
Project description:BackgroundCurrent network-based microarray analysis uses the information of interactions among concerned genes/gene products, but still considers each gene expression individually. We propose an organized knowledge-supervised approach - Integrative eXpression Profiling (IXP), to improve microarray classification accuracy, and help discover groups of genes that have been too weak to detect individually by traditional ways. To implement IXP, ant colony optimization reordering (ACOR) algorithm is used to group functionally related genes in an ordered way.ResultsUsing Alzheimer's disease (AD) as an example, we demonstrate how to apply ACOR-based IXP approach into microarray classifications. Using a microarray dataset - GSE1297 with 31 samples as training set, the result for the blinded classification on another microarray dataset - GSE5281 with 151 samples, shows that our approach can improve accuracy from 74.83% to 82.78%. A recently-published 1372-probe signature for AD can only achieve 61.59% accuracy in the same condition. The ACOR-based IXP approach also has better performance than the IXP approach based on classic network ranking, graph clustering, and random-ordering methods in an overall classification performance comparison.ConclusionsThe ACOR-based IXP approach can serve as a knowledge-supervised feature transformation approach to increase classification accuracy dramatically, by transforming each gene expression profile to an integrated expression files as features inputting into standard classifiers. The IXP approach integrates both gene expression information and organized knowledge - disease gene/protein network topology information, which is represented as both network node weights (local topological properties) and network node orders (global topological characteristics).
| S-EPMC3583189 | biostudies-literature
Project description:Personalized medicine is the future of medical practice. In oncology, tumor heterogeneity assessment represents a pivotal step for effective treatment planning and prognosis prediction. Despite new procedures for DNA sequencing and analysis, non-invasive methods for tumor characterization are needed to impact on daily routine. On purpose, imaging texture analysis is rapidly scaling, holding the promise to surrogate histopathological assessment of tumor lesions. In this work, we propose a tree-based representation strategy for describing intra-tumor heterogeneity of patients affected by metastatic cancer. We leverage radiomics information extracted from PET/CT imaging and we provide an exhaustive and easily readable summary of the disease spreading. We exploit this novel patient representation to perform cancer subtyping according to hierarchical clustering technique. To this purpose, a new heterogeneity-based distance between trees is defined and applied to a case study of prostate cancer. Clusters interpretation is explored in terms of concordance with severity status, tumor burden and biological characteristics. Results are promising, as the proposed method outperforms current literature approaches. Ultimately, the proposed method draws a general analysis framework that would allow to extract knowledge from daily acquired imaging data of patients and provide insights for effective treatment planning.
| S-EPMC9666477 | biostudies-literature
Project description:Crystallography and NMR system (CNS) is currently a widely used method for fragment-free ab initio protein folding from inter-residue distance or contact maps. Despite its widespread use in protein structure prediction, CNS is a decade-old macromolecular structure determination system that was originally developed for solving macromolecular geometry from experimental restraints as opposed to predictive modeling driven by interaction map data. As such, the adaptation of the CNS experimental structure determination protocol for ab initio protein folding is intrinsically anomalous that may undermine the folding accuracy of computational protein structure prediction. In this paper, we propose a new CNS-free hierarchical structure modeling method called DConStruct for folding both soluble and membrane proteins driven by distance and contact information. Rigorous experimental validation shows that DConStruct attains much better reconstruction accuracy than CNS when tested with the same input contact map at varying contact thresholds. The hierarchical modeling with iterative self-correction employed in DConStruct scales at a much higher degree of folding accuracy than CNS with the increase in contact thresholds, ultimately approaching near-optimal reconstruction accuracy at higher-thresholded contact maps. The folding accuracy of DConStruct can be further improved by exploiting distance-based hybrid interaction maps at tri-level thresholding, as demonstrated by the better performance of our method in folding free modeling targets from the 12th and 13th rounds of the Critical Assessment of techniques for protein Structure Prediction (CASP) experiments compared to popular CNS- and fragment-based approaches and energy-minimization protocols, some of which even using much finer-grained distance maps than ours. Additional large-scale benchmarking shows that DConStruct can significantly improve the folding accuracy of membrane proteins compared to a CNS-based approach. These results collectively demonstrate the feasibility of greatly improving the accuracy of ab initio protein folding by optimally exploiting the information encoded in inter-residue interaction maps beyond what is possible by CNS.
| S-EPMC7935296 | biostudies-literature
Project description:BACKGROUND:In unsupervised learning and clustering, data integration from different sources and types is a difficult question discussed in several research areas. For instance in omics analysis, dozen of clustering methods have been developed in the past decade. When a single source of data is at play, hierarchical clustering (HC) is extremely popular, as a tree structure is highly interpretable and arguably more informative than just a partition of the data. However, applying blindly HC to multiple sources of data raises computational and interpretation issues. RESULTS:We propose mergeTrees, a method that aggregates a set of trees with the same leaves to create a consensus tree. In our consensus tree, a cluster at height h contains the individuals that are in the same cluster for all the trees at height h. The method is exact and proven to be [Formula: see text], n being the individuals and q being the number of trees to aggregate. Our implementation is extremely effective on simulations, allowing us to process many large trees at a time. We also rely on mergeTrees to perform the cluster analysis of two real -omics data sets, introducing a spectral variant as an efficient and robust by-product. CONCLUSIONS:Our tree aggregation method can be used in conjunction with hierarchical clustering to perform efficient cluster analysis. This approach was found to be robust to the absence of clustering information in some of the data sets as well as an increased variability within true clusters. The method is implemented in R/C++ and available as an R package named mergeTrees, which makes it easy to integrate in existing or new pipelines in several research areas.
| S-EPMC7085155 | biostudies-literature
Project description:MotivationSeeding is a rate-limiting stage in sequence alignment for next-generation sequencing reads. The existing optimization algorithms typically utilize hardware and machine-learning techniques to accelerate seeding. However, an efficient solution provided by professional next-generation sequencing compressors has been largely overlooked by far. In addition to achieving remarkable compression ratios by reordering reads, these compressors provide valuable insights for downstream alignment that reveal the repetitive computations accounting for more than 50% of seeding procedure in commonly used short read aligner BWA-MEM at typical sequencing coverage. Nevertheless, the exploited redundancy information is not fully realized or utilized.ResultsIn this study, we present a compressive seeding algorithm, named CompSeed, to fill the gap. CompSeed, in collaboration with the existing reordering-based compression tools, finishes the BWA-MEM seeding process in about half the time by caching all intermediate seeding results in compact trie structures to directly answer repetitive inquiries that frequently cause random memory accesses. Furthermore, CompSeed demonstrates better performance as sequencing coverage increases, as it focuses solely on the small informative portion of sequencing reads after compression. The innovative strategy highlights the promising potential of integrating sequence compression and alignment to tackle the ever-growing volume of sequencing data.Availability and implementationCompSeed is available at https://github.com/i-xiaohu/CompSeed.
| S-EPMC10955252 | biostudies-literature
Project description:The effects of hemodynamic changes in the developing brain have yet to be fully understood. The aim of this study was to explore the relationship between perturbations of the cerebral blood flow in the developing brain via unilateral hypoperfusion in P7 rats. As expected, nuclear caspase-3 (casp3) cleavage and DNA fragmentation were detected at 48 hours after stroke in the injured cortex. Surprisingly, casp3 was also cleaved in the contralateral cortex, although without cell death markers. Delayed (48 hours) casp3 cleavage without DNA fragmentation was also identified after unilateral common carotid artery occlusion, both in the hypoperfused cortex and the unaffected cortex, producing mirror images. Upstream calpain activation, caspase-2 cleavage, and mitochondrial cytochrome c release initiated casp3 cleavage, but did not produce preconditioning. The neuronal marker NeuN co-localized with cleaved casp3 in cortical layers II-III and VI and with gaba-amino butyric acid in layer III. Indeed, collateral supply was provided from the opposite side during carotid artery occlusion but not after reperfusion, and the number of cleaved casp3-positive cells significantly negatively correlated with the common carotid artery immediate reperfusion percentage. In summary, unilateral hypoperfusion, while insufficient to induce cell death, may active bilateral and symmetric casp3 in the P7 rat brain. Additionally, the opposite healthy hemisphere is altered due to the injury and thus should not be used as an internal control.
| S-EPMC2774074 | biostudies-literature
Project description:The recyclable utilization of waste biomass is increasingly important for the development of a sustainable society. Here, the sawdust-derived activated carbon (SD-AC) has been prepared via a convenient H3PO4-based activation method and further trialed as an electrode for use as a high-performance symmetric supercapacitor. The as-prepared SD-AC possesses a hierarchically porous structure with micropores (0.55 nm) and mesopores (2.58 nm), accounting for its high specific surface area of 621 m2 g-1, with a pore volume of 0.35 cm3 g-1. Such a hierarchically porous structure can offer a favorable pathway for fast ion penetration and transportation, enhancing its electrochemical performance. As a result, the SD-AC electrode exhibits a maximum specific capacitance of up to 244.1 F g-1 at 1.0 A g-1, a high rate capability (129.06 F g-1 at 20 A g-1), and an excellent cycling performance, with 87% retention over 10,000 cycles at 10 A g-1. Of particular note is that the SD-AC-based symmetric supercapacitor achieves a maximum energy density of 19.9 Wh kg-1 at the power density of 650 W kg-1, with a long-term cycle lifespan. This work showcases the recyclable utilization of waste biomass for the preparation of high-value activated carbon for efficient energy storage.
| S-EPMC8912637 | biostudies-literature
Project description:Relationships between tree size and water use indicate how soil water is partitioned between differently sized individuals, and hence competition for water. These relationships are rarely examined, let alone whether there is consistency in shape across populations. Competition for water among plants is often assumed to be size-symmetric, i.e., exponents (b1) of power functions (water use ∝ biomassb1) equal to 1, with all sizes using the same amount of water proportionally to their size. We tested the hypothesis that b1 actually varies greatly, and based on allometric theory, that b1 is only centered around 1 when size is quantified as basal area or sapwood area (not diameter). We also examined whether b1 varies spatially and temporally in relation to stand structure (height and density) and climate. Tree water use ∝ sizeb1 power functions were fitted for 80 species and 103 sites using the global SAPFLUXNET database. The b1 were centered around 1 when tree size was given as basal area or sapwood area, but not as diameter. The 95% confidence intervals of b1 included the theoretical predictions for the scaling of plant vascular networks. b1 changed through time within a given stand for the species with the longest time series, such that larger trees gained an advantage during warmer and wetter conditions. Spatial comparisons across the entire dataset showed that b1 correlated only weakly (R2 < 12%) with stand structure or climate, suggesting that inter-specific variability in b1 and hence the symmetry of competition for water may be largely related to inter-specific differences in tree architecture or physiology rather than to climate or stand structure. In conclusion, size-symmetric competition for water (b1 ≈ 1) may only be assumed when size is quantified as basal area or sapwood area, and when describing a general pattern across forest types and species. There is substantial deviation in b1 between individual stands and species.
| S-EPMC9838098 | biostudies-literature