SEARCH · PubMed Health

Results for “Clustering Algorithms”

Explore indexed PubMed citations for clinical trials, systematic reviews and public health research. Read source abstracts and follow each citation to its original PubMed record.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 1,765 records · Page 98Linked to original sources

PubMed2005

Sparse factorizations of gene expression data guided by binding data.

Existing clustering methods do not deal well with overlapping clusters, are unstable and do not take into account the robustness of biological systems, or more complex background knowledge such as regulator binding data. Here we describe a nonnegative sparse factorization algorithm dealing with the above problems: cluster overlaps are allowed by design, the nonnegativity constraints implicitly approximate the robustness of biological systems and regulator binding data is used to guide the factorization. Preliminary results show the feasibility of our approach.

Algorithms↗

PubMed2025

Unsupervised multiscale clustering of single-cell transcriptomes to identify hierarchical structures of cell subtypes.

BACKGROUND: Cell clustering is an essential step in uncovering cellular architectures in single-cell RNA sequencing (scRNA-seq) data. However, the existing cell clustering approaches are not well designed to dissect complex structures of cellular landscapes at a finer resolution. RESULTS: Here, we develop a multiscale clustering (MSC) approach to construct a sparse cell-cell correlation network for unsupervised identification of de novo cell types and subtypes across multiple resolutions. Based upon simulated silver- and gold-standard data as well as real scRNA-seq data in diseases, MSC demonstrates significantly improved performance compared to established benchmark methods and reveals a biologically meaningful cell hierarchy to facilitate the discovery of novel disease-associated cell subtypes and mechanisms. CONCLUSIONS: We present MSC as a new single-cell multiscale clustering framework as a powerful tool for advancing discoveries in disease-associated cell populations using single-cell sequencing data.

Single-Cell Analysis↗

PubMed2004

Clustered organization of cortical connectivity.

Long-range corticocortical connectivity in mammalian brains possesses an intricate, nonrandom organization. Specifically, projections are arranged in "small-world" networks, forming clusters of cortical areas, which are closely linked among each other, but less frequently with areas in other clusters. In order to delineate the structure of cortical clusters and identify their members, we developed a computational approach based on evolutionary optimization. In different compilations of connectivity data for the cat and macaque monkey brain, the algorithm identified a small number of clusters that broadly agreed with functional cortical subdivisions. We propose a simple spatial growth model for evolving clustered connectivity, and discuss structural and functional implications of the clustered, small-world organization of cortical networks.

Animals↗

PubMed1994

Tree-structured non-linear filter and wavelet transform for microcalcification segmentation in digital mammography.

A novel algorithm was developed for computer aided diagnosis of microcalcification clusters in digital mammography. The method includes: (a) tree-structured central weighted median filters with variable shape windowing to suppress image noise but preserve image details; (b) a quasi range dispersion edge detector to increase edge contrast and definition; and (c) tree-structured wavelets for calcification segmentation. The preliminary evaluation of the method on nine mammograms showed that 100% sensitivity can be achieved at the expense of four false positive clusters per image. Research is ongoing for further optimization of the algorithm to reduce the number of false alarms and establish its clinical value.

Algorithms↗

PubMed2005

pSLIP: SVM based protein subcellular localization prediction using multiple physicochemical properties.

BACKGROUND: Protein subcellular localization is an important determinant of protein function and hence, reliable methods for prediction of localization are needed. A number of prediction algorithms have been developed based on amino acid compositions or on the N-terminal characteristics (signal peptides) of proteins. However, such approaches lead to a loss of contextual information. Moreover, where information about the physicochemical properties of amino acids has been used, the methods employed to exploit that information are less than optimal and could use the information more effectively. RESULTS: In this paper, we propose a new algorithm called pSLIP which uses Support Vector Machines (SVMs) in conjunction with multiple physicochemical properties of amino acids to predict protein subcellular localization in eukaryotes across six different locations, namely, chloroplast, cytoplasmic, extracellular, mitochondrial, nuclear and plasma membrane. The algorithm was applied to the dataset provided by Park and Kanehisa and we obtained prediction accuracies for the different classes ranging from 87.7%-97.0% with an overall accuracy of 93.1%. CONCLUSION: This study presents a physicochemical property based protein localization prediction algorithm. Unlike other algorithms, contextual information is preserved by dividing the protein sequences into clusters. The prediction accuracy shows an improvement over other algorithms based on various types of amino acid composition (single, pair and gapped pair). We have also implemented a web server to predict protein localization across the six classes (available at http://pslip.bii.a-star.edu.sg/).

Algorithms↗

PubMed2004

Classification and knowledge discovery in protein databases.

We consider the problem of classification in noisy, high-dimensional, and class-imbalanced protein datasets. In order to design a complete classification system, we use a three-stage machine learning framework consisting of a feature selection stage, a method addressing noise and class-imbalance, and a method for combining biologically related tasks through a prior-knowledge based clustering. In the first stage, we employ Fisher's permutation test as a feature selection filter. Comparisons with the alternative criteria show that it may be favorable for typical protein datasets. In the second stage, noise and class imbalance are addressed by using minority class over-sampling, majority class under-sampling, and ensemble learning. The performance of logistic regression models, decision trees, and neural networks is systematically evaluated. The experimental results show that in many cases ensembles of logistic regression classifiers may outperform more expressive models due to their robustness to noise and low sample density in a high-dimensional feature space. However, ensembles of neural networks may be the best solution for large datasets. In the third stage, we use prior knowledge to partition unlabeled data such that the class distributions among non-overlapping clusters significantly differ. In our experiments, training classifiers specialized to the class distributions of each cluster resulted in a further decrease in classification error.

Algorithms↗

PubMed1998

Rough annealing by two-step clustering, with application to neuronal signals.

To accomplish analyses on the properties of neuronal populations it is mandatory that each unit activity is identified within the overall noise background and the other unit signals merged in the same trace. The problem, addressed as a clustering one, is particularly difficult as no assumption can be made on the prior data distribution. We propose an algorithm that achieves this goal by a two-phase agglomerative hierarchical clustering. First, an inflated estimation (overly) of the number of clusters is cast down and, by a maximum entropy principle (MEP) approach, is made to collapse towards an arrangement near natural ones. In the second step consecutive partitions are created by merging, two at time previously aggregated partitions, according to similarity criteria, in order to reveal a cluster solution. The procedure makes no assumptions about data distributions and guarantees high robustness with respect to noise. An application on real data out of multiple unit recordings from spinal cord neurons of mixed gas-anaesthetized rats is presented.

Algorithms↗

PubMed2004

Calculation of excited-state properties using general coupled-cluster and configuration-interaction models.

Using string-based algorithms excitation energies and analytic first derivatives for excited states have been implemented for general coupled-cluster (CC) models within CC linear-response (LR) theory which is equivalent to the equation-of-motion (EOM) CC approach for these quantities. Transition moments between the ground and excited states are also considered in the framework of linear-response theory. The presented procedures are applicable to both single-reference-type and multireference-type CC wave functions independently of the excitation manifold constituting the cluster operator and the space in which the effective Hamiltonian is diagonalized. The performance of different LR-CC/EOM-CC and configuration-interaction approaches for excited states is compared. The effect of higher excitations on excited-state properties is demonstrated in benchmark calculations for NH(2) and NH(3). As a first application, the stationary points of the S(1) surface of acetylene are characterized by high-accuracy calculations.

Journal Article↗

PubMed2006

A single-particle characterization of a mobile Versatile Aerosol Concentration Enrichment System for exposure studies.

BACKGROUND: An Aerosol Time-of-Flight Mass Spectrometer (ATOFMS) was used to investigate the size and chemical composition of fine concentrated ambient particles (CAPs) in the size range 0.2-2.6 microm produced by a Versatile Aerosol Concentration Enrichment System (VACES) contained within the Mobile Ambient Particle Concentrator Exposure Laboratory (MAPCEL). The data were collected during a study of human exposure to CAPs, in Edinburgh (UK), in February-March 2004. The air flow prior to, and post, concentration in the VACES was sampled in turn into the ATOFMS, which provides simultaneous size and positive and negative mass spectral data on individual fine particles. RESULTS: The particle size distribution was unaltered by the concentrator over the size range 0.2-2.6 microm, with an average enrichment factor during this study of approximately 5 (after dilution of the final air stream). The mass spectra from single particles were objectively grouped into 20 clusters using the multivariate K-means algorithm and then further grouped manually, according to similarity in composition and time sequence, into 8 main clusters. The particle ensemble was dominated by pure and reacted sea salt and other coarse inorganic dusts (as a consequence of the prevailing maritime-source climatology during the study), with relatively minor contributions from carbonaceous and secondary material. Very minor variations in particle composition were noted pre- and post-particle concentration, but overall there was no evidence of any significant change in particle composition. CONCLUSION: These results confirm, via single particle analysis, the preservation of the size distribution and chemical composition of fine ambient PM in the size range 0.2-2.6 microm after passage through the VACES concentration instrumentation.

Journal Article↗

PubMed2004

Variable-branch tree-structured vector quantization.

Tree-structured vector quantizers (TSVQ) and their variants have recently been proposed. All trees used are fixed M-ary tree structured, such that the training samples in each node must be artificially divided into a fixed number of clusters. This paper proposes a variable-branch tree-structured vector quantizer (VBTSVQ) based on a genetic algorithm, which searches for the number of child nodes of each splitting node for optimal coding in VBTSVQ. Moreover, one disadvantage of TSVQ is that the searched codeword usually differs from the full searched codeword. Briefly, the searched codeword in TSVQ sometimes is not the closest codeword to the input vector. This paper proposes the multiclassification encoding method to select many classified components to represent each cluster, and the codeword encoded in the VBTSVQ is usually the same as that of the full search. VBTSVQ outperforms other TSVQs in the experiments presented here.

Algorithms↗

PubMed2005

A local correlation model that yields intrinsically smooth potential-energy surfaces.

We demonstrate an algorithm for computing local coupled-cluster doubles (LCCD) energies that form rigorously smooth potential-energy surfaces and which should be fast enough for application to large systems in the future. Like previous LCCD algorithms, our method solves iteratively for only a limited number of correlation amplitudes, treating the remaining amplitudes with second-order perturbation theory. However, by employing bump functions, our method smoothes the transition from iteratively solved amplitude to perturbation-treated amplitude, invoking the implicit function theorem to prove that our LCCD energy is an infinitely differentiable function of nuclear coordinates. We make no explicit amplitude domains nor do we rely on the existence of atom-centered, redundant orbitals in order to get smooth potential-energy curves. In fact, our algorithm employs only localized orthonormal occupied and virtual orbitals. Our approach should be applicable to many other electron correlation methods.

Journal Article↗

PubMed2000

Designing safe job rotation schedules using optimization and heuristic search.

Job rotation is one method that is sometimes used to reduce exposure to strenuous materials handling; however, developing effective rotation schedules can be complex in even moderate sized facilities. The purpose of this research is to develop methods of incorporating safety criteria into scheduling algorithms to produce job rotation schedules that reduce the potential for injury. Integer programming and a genetic algorithm were used to construct job rotation schedules. Schedules were comprised of lifting tasks whose potential for causing injury was assessed with the Job Severity Index. Each method was used to design four job rotation schedules that met specified safety criteria in a working environment where the object weight, horizontal distance and repetition rate varied over time. Each rotation was assigned to a specific gender/lifting capacity group. Five versions of the integer programming search method were applied to this problem. Each version generated one job rotation schedule. The genetic algorithm model was able to create a population of 437 feasible solutions to the rotation problem. Utilizing cluster analysis, a rule set was derived from the genetic algorithm generated solutions. These rules provided guidelines for designing safe job rotation schedules without the use of a computer. The advantages and limitations of these approaches in developing administrative controls for the prevention of back injury are discussed.

Algorithms↗

PubMed2002

A hierarchical Poisson mixture regression model to analyse maternity length of hospital stay.

Inpatient length of stay (LOS) is often considered as a proxy of hospital resource consumption. Using statewide obstetrical delivery data, a two-component Poisson mixture model provides a reasonable fit to the heterogeneous LOS distribution. Adopting the generalized linear mixed model (GLMM) approach, random effects are introduced to the two-component Poisson mixture regression model to account for the inherent correlation of patients clustered within hospitals. An EM algorithm is developed for the joint estimation of regression coefficients and variance component parameters. Related diagnostic measures for assessing model adequacy are derived. When applying the method to analyse maternity LOS, appropriate risk factors for the short-stay and long-stay subgroups can be identified from the respective Poisson components. In addition, predicted random hospital effects enable the comparison of relative efficiencies among hospitals after adjustment for patient case-mix and health provision characteristics.

Adult↗

PubMed1999

New efficient statistical sequence-dependent structure prediction of short to medium-sized protein loops based on an exhaustive loop classification.

A bank of 13,563 loops from three to eight amino acid residues long, representing motifs between two consecutive regular secondary structures, has been derived from protein structures presenting less than 95 % sequence identity. Statistical analyses of occurrences of conformations and residues revealed length-dependent over-representations of particular amino acids (glycine, proline, asparagine, serine, and aspartate) and conformations (alphaL, epsilon, betaPregions of the Ramachandran plot). A position-dependent distribution of these occurrences was observed for N and C-terminal residues, which are correlated to the nature of the flanking regions. Loops of the same length were clustered into statistically meaningful families on the basis of their backbone structures when placed in a common reference frame, independent of the flanks. These clusters present significantly different distributions of sequence, conformations, and endpoint residue Calphadistances. On the basis of the sequence-structure correlation of this clustering, an automatic loop modeling algorithm was developed. Based on the knowledge of its sequence and of its flank backbone structures each query loop is assigned to a family and target loop supports are selected in this family. The support backbones of these target loops are then adjusted on flanking structures by partial exploration of the conformational space. Loop closure is performed by energy minimization for each support and the final model is chosen among connected supports based upon energy criteria. The quality of the prediction is evaluated by the root-mean-square deviation (rmsd) between the final model and the native loops when the whole bank is re-attributed on itself with a Jackknife test. This average rmsd ranges from 1.1 A for three-residue loops to 3.8 A for eight-residue loops. A few poorly predicted loops are inescapable, considering the high level of diversity in loops and the lack of environment data. To overcome such modeling problems, a statistical reliability score was assigned for each prediction. This score is correlated to the quality of the prediction, in terms of rmsd, and thus improves the selection accuracy of the model. The algorithm efficiency was compared to CASP3 target loop predictions. Moreover, when tested on a test loop bank, this algorithm was shown to be robust when the loops are not precisely delimited, therefore proving to be a useful tool in practice for protein modeling.

Models, Molecular↗

PubMed1988

An evolutionary tree for invertebrate globin sequences.

A phylogenetic tree was constructed from 245 globin amino acid sequences. Of the six plant globins, five represented the Leguminosae and one the Ulmaceae. Among the invertebrate sequences, 7 represented the phylum Annelida, 13 represented Insecta and Crustacea of the phylum Arthropoda, and 6 represented the phylum Mollusca. Of the vertebrate globins, 4 represented the Agnatha and 209 represented the Gnathostomata. A common alignment was achieved for the 245 sequences using the parsimony principle, and a matrix of minimum mutational distances was constructed. The most parsimonious phylogenetic tree, i.e., the one having the lowest number of nucleotide substitutions that cause amino acid replacements, was obtained employing clustering and branch-swapping algorithms. Based on the available fossil record, the earliest split in the ancestral metazoan lineage was placed at 680 million years before present (Myr BP), the origin of vertebrates was placed at 510 Myr BP, and the separation of the Chondrichthyes and the Osteichthyes was placed at 425 Myr BP. Local "molecular clock" calculations were used to date the branch points on the descending branches of the various lineages within the plant and invertebrate portions of the tree. The tree divided the 245 sequences into five distinct clades that corresponded exactly to the five groups plants, annelids, arthropods, molluscs, and vertebrates. Furthermore, the maximum parsimony tree, in contrast to the unweighted pair group and distance Wagner trees, was consistent with the available fossil record and supported the hypotheses that the primitive hemoglobin of metazoans was monomeric and that the multisubunit extracellular hemoglobins found among the Annelida and the Arthropoda represent independently derived states.

Amino Acid Sequence↗

PubMed1987

Refined crystal structure of dogfish M4 apo-lactate dehydrogenase.

The crystal structure of M4 apo-lactate dehydrogenase from the spiny dogfish (Squalus acanthius) was initially refined by a constrained-restrained, and subsequently restrained, least-squares technique. The final structure contained 286 water molecules and two sulfate ions per subunit and gave an R-factor of 0.202 for difraction data between 8.0 and 2.0 A resolution. The upper limit for the co-ordinate accuracy of the atoms was estimated to be 0.25 A. The elements of secondary structure of the refined protein have not changed from those described previously, except for the appearance of a one-and-a-half turn 3(10) helix immediately after beta J. There is also a short segment of 3(10) helix between beta C and beta D in the part of the chain that connects the two beta alpha beta alpha beta units of the six-stranded parallel sheet (residues Tyr83 to Ala87). Examination of the interactions among the different elements of secondary structure by means of a surface accessibility algorithm supports the four structural clusters in the subunit. The first of the two sulfate ions is in the active site and occupies a cavity near the essential His195. Its nearest protein ligands are Arg171, Asp168 and Asn140. The second sulfate ion is located near the P-axis subunit interface. It is liganded by His188 and Arg173. These two residues are conserved in bacterial lactate dehydrogenase and form part of the fructose 1,6-bisphosphate effector binding site. Two other data sets in which one (collected at pH 7.8) or both (collected at pH 6.0) sulfate ions were replaced by citrate ions were also analyzed. Five cycles of refinement with respect to the pH 6.0 data (25 to 2.8 A resolution) resulted in an R value of 0.191. Only water molecules occupy the subunit boundary anion binding site at pH 7.8. The amino acid sequence was found to be in poor agreement with (2Fobs-Fcalc) electron density maps for the peptide between residues 207 and 211. The original sequence WNALKE was replaced by NVASIK. The essential His195 is hydrogen bonded to Asp168 on one side and Asn140 on the other. The latter residue is part of a turn that contains the only cis peptide bond of the structure at Pro141. The "flexible loop" (residues 97 to 123), which folds down over the active center in ternary complexes of the enzyme with substrate and coenzyme, has a well-defined structure. Analysis of the environment of Tyr237 suggests how its chemical modification inhibits the enzyme.

Amino Acid Sequence↗

PubMed2006

Linkage disequilibrium between alleles at highly polymorphic mini- and micro-satellite loci of Theileria parva isolated from cattle in three regions of Kenya.

Theileria parva schizont-infected lymphocyte culture isolates from western, central and coastal Kenya were analysed for size polymorphism at 30 T. parva-specific variable number tandem repeat (VNTR) loci using a panel of mini- and micro-satellite markers. The mean number of alleles ranged from 3 to 11 at individual loci and 183 distinct alleles were observed in total, indicating high genetic diversity within the T. parva gene pool in Kenyan cattle. The frequency distribution of the length variation of specific alleles among isolates ranged from normal to markedly discontinuous. Genetic relationships between isolates were analysed using standard indices of genetic distance. Genetic distances and dendrograms derived from these using neighbour-joining algorithms did not indicate significant clustering on a geographical basis. Analysis of molecular variance demonstrated that the genetic variation between individual isolates was 72%, but only 2.3% when isolates from different regions were pooled. Both these observations suggest minimal genetic sub-structuring relative to geographical origin. Linkage disequilibrium was observed between pairs of loci within populations, as in certain Ugandan T. parva populations. A novel observation was that disequilibrium was also detected between alleles at three individual pairs of VNTR loci when isolates from the three regional meta-populations were pooled for analysis.

Alleles↗

PubMed2005

Future perspectives for intraoperative MRI.

MRI-guided neurosurgery not only represents a technical challenge but a transformation from conventional hand-eye coordination to interactive navigational operations. In the future, multimodality-based images will be merged into a single model, in which anatomy and pathologic changes are at once distinguished and integrated into the same intuitive framework. The long-term goals of improving surgical procedures and attendant outcomes, reducing costs, and achieving broad use can be achieved with a three-pronged approach: 1. Improving the presentation of preoperative and real-time intraoperative image information 2. Integrating imaging and treatment-related technology into therapy delivery systems 3. Testing the clinical utility of image guidance in surgery The recent focus in technology development is on improving our ability to understand and apply medical images and imaging systems. Areas of active research include image processing, model-based image analysis, model deformation, real-time registration, real-time 3D (so-called "four-dimensional") imaging, and the integration and presentation of image and sensing information in the operating room. Key elements of the technical matrix also include visualization and display platforms and related software for information and display, model-based image understanding, the use of computing clusters to speed computation (ie, algorithms with partitioned computation to optimize performance), and advanced devices and systems for 3D device tracking (navigation). Current clinical applications are successfully incorporating real-time and/or continuously up-dated image-based information for direct intra-operative visualization. In addition to using traditional imaging systems during surgery, we foresee optimized use of molecular marker technology, direct measures of tissue characterization (ie, optical measurements and/or imaging), and integration of the next generation of surgical and therapy devices (including image-guided robotic systems). Although we expect the primary clinical thrusts of MRI-guided therapy to remain in neurosurgery, with the possible addition of other areas like orthopedic, head, neck, and spine surgery, we also anticipate increased use of image-guided focal thermal ablative methods (eg, laser, RF, cryoablation, high-intensity focused ultrasound). By validating the effectiveness of MRI-guided therapy in specific clinical procedures while refining the technology that serves as its underpinning at the same time, we expect many neurosurgeons will eventually embrace MRI as their intraoperative imaging choice. Clearly, intraoperative MRI offers several palpable advantages. Most important among these are improved medical outcomes, shorter hospitalization, and better and faster procedures with fewer complications. Certain economic and practical barriers also impede the large-scale use of intraoperative MRI. Although there has been a concerted technical effort to increase the benefit/cost ratio by gathering more accurate information, designing more localized and less invasive treatment devices, and developing better methods to orient and position therapy end-effectors, further research is needed. Indeed, the drive to improve and upgrade technology is ongoing. Specifically, in the context of the real-time representation of the patient's anatomy, we have improved the quality and utility of the information presented to the surgeon, which, in turn, contributes to more successful surgical outcomes. We can also expect improvements in intraoperative imaging systems as well as increased use of nonimaging sensors and robotics to facilitate more widespread use of intraoperative MRI.

Humans↗