PubMed Health⌕ Search

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,135 records · Page 63Linked to original sources
PubMed2005

Syntons, metabolons and interactons: an exact graph-theoretical approach for exploring neighbourhood between genomic and functional data.

MOTIVATION: Modern comparative genomics does not restrict to sequence but involves the comparison of metabolic pathways or protein-protein interactions as well. Central in this approach is the concept of neighbourhood between entities (genes, proteins, chemical compounds). Therefore there is a growing need for new methods aiming at merging the connectivity information from different biological sources in order to infer functional coupling. RESULTS: We present a generic approach to merge the information from two or more graphs representing biological data. The method is based on two concepts. The first one, the correspondence multigraph, precisely defines how correspondence is performed between the primary data-graphs. The second one, the common connected components, defines which property of the multigraph is searched for. Although this problem has already been informally stated in the past few years, we give here a formal and general statement together with an exact algorithm to solve it. AVAILABILITY: The algorithm presented in this paper has been implemented in C. Source code is freely available for download at: http://www.inrialpes.fr/helix/people/viari/cccpart.

Algorithms↗
PubMed2005

ClaNC: point-and-click software for classifying microarrays to nearest centroids.

SUMMARY: ClaNC (classification to nearest centroids) is a simple and an accurate method for classifying microarrays. This document introduces a point-and-click interface to the ClaNC methodology. The software is available as an R package. AVAILABILITY: ClaNC is freely available from http://students.washington.edu/adabney/clanc

Algorithms↗
PubMed2005

Quality classification of tandem mass spectrometry data.

UNLABELLED: Peptide identification by tandem mass spectrometry is an important tool in proteomic research. Powerful identification programs exist, such as SEQUEST, ProICAT and Mascot, which can relate experimental spectra to the theoretical ones derived from protein databases, thus removing much of the manual input needed in the identification process. However, the time-consuming validation of the peptide identifications is still the bottleneck of many proteomic studies. One way to further streamline this process is to remove those spectra that are unlikely to provide a confident or valid peptide identification, and in this way to reduce the labour from the validation phase. RESULTS: We propose a prefiltering scheme for evaluating the quality of spectra before the database search. The spectra are classified into two classes: spectra which contain valuable information for peptide identification and spectra that are not derived from peptides or contain insufficient information for interpretation. The different spectral features developed for the classification are tested on a real-life material originating from human lymphoblast samples and on a standard mixture of 9 proteins, both labelled with the ICAT-reagent. The results show that the prefiltering scheme efficiently separates the two spectra classes.

Algorithms↗
PubMed2005

EDGE: extraction and analysis of differential gene expression.

EDGE (Extraction of Differential Gene Expression) is an open source, point-and-click software program for the significance analysis of DNA microarray experiments. EDGE can perform both standard and time course differential expression analysis. The functions are based on newly developed statistical theory and methods. This document introduces the EDGE software package.

Algorithms↗
PubMed2006

Effective similarity measures for expression profiles.

It is commonly accepted that genes with similar expression profiles are functionally related. However, there are many ways one can measure the similarity of expression profiles, and it is not clear a priori what is the most effective one. Moreover, so far no clear distinction has been made as for the type of the functional link between genes as suggested by microarray data. Similarly expressed genes can be part of the same complex as interacting partners; they can participate in the same pathway without interacting directly; they can perform similar functions; or they can simply have similar regulatory sequences. Here we conduct a study of the notion of functional link as implied from expression data. We analyze different similarity measures of gene expression profiles and assess their usefulness and robustness in detecting biological relationships by comparing the similarity scores with results obtained from databases of interacting proteins, promoter signals and cellular pathways, as well as through sequence comparisons. We also introduce variations on similarity measures that are based on statistical analysis and better discriminate genes which are functionally nearby and faraway. Our tools can be used to assess other similarity measures for expression profiles, and are accessible at biozon.org/tools/expression/

Algorithms↗
PubMed2006

Improved scoring of functional groups from gene expression data by decorrelating GO graph structure.

MOTIVATION: The result of a typical microarray experiment is a long list of genes with corresponding expression measurements. This list is only the starting point for a meaningful biological interpretation. Modern methods identify relevant biological processes or functions from gene expression data by scoring the statistical significance of predefined functional gene groups, e.g. based on Gene Ontology (GO). We develop methods that increase the explanatory power of this approach by integrating knowledge about relationships between the GO terms into the calculation of the statistical significance. RESULTS: We present two novel algorithms that improve GO group scoring using the underlying GO graph topology. The algorithms are evaluated on real and simulated gene expression data. We show that both methods eliminate local dependencies between GO terms and point to relevant areas in the GO graph that remain undetected with state-of-the-art algorithms for scoring functional terms. A simulation study demonstrates that the new methods exhibit a higher level of detecting relevant biological terms than competing methods.

Algorithms↗
PubMed2006

Exploiting indirect neighbours and topological weight to predict protein function from protein-protein interactions.

MOTIVATION: Most approaches in predicting protein function from protein-protein interaction data utilize the observation that a protein often share functions with proteins that interacts with it (its level-1 neighbours). However, proteins that interact with the same proteins (i.e. level-2 neighbours) may also have a greater likelihood of sharing similar physical or biochemical characteristics. We speculate that functional similarity between a protein and its neighbours from the two different levels arise from two distinct forms of functional association, and a protein is likely to share functions with its level-1 and/or level-2 neighbours. We are interested in finding out how significant is functional association between level-2 neighbours and how they can be exploited for protein function prediction. RESULTS: We made a statistical study on recent interaction data and observed that functional association between level-2 neighbours is clearly observable. A substantial number of proteins are observed to share functions with level-2 neighbours but not with level-1 neighbours. We develop an algorithm that predicts the functions of a protein in two steps: (1) assign a weight to each of its level-1 and level-2 neighbours by estimating its functional similarity with the protein using the local topology of the interaction network as well as the reliability of experimental sources and (2) scoring each function based on its weighted frequency in these neighbours. Using leave-one-out cross validation, we compare the performance of our method against that of several other existing approaches and show that our method performs relatively well.

Algorithms↗
PubMed2006

Modified signal-to-noise: a new simple and practical gene filtering approach based on the concept of projective adaptive resonance theory (PART) filtering method.

UNLABELLED: Considering the recent advances in and the benefits of DNA microarray technologies, many gene filtering approaches have been employed for the diagnosis and prognosis of diseases. In our previous study, we developed a new filtering method, namely, the projective adaptive resonance theory (PART) filtering method. This method was effective in subclass discrimination. In the PART algorithm, the genes with a low variance in gene expression in either class, not both classes, were selected as important genes for modeling. Based on this concept, we developed novel simple filtering methods such as modified signal-to-noise (S2N') in the present study. The discrimination model constructed using these methods showed higher accuracy with higher reproducibility as compared with many conventional filtering methods, including the t-test, S2N, NSC and SAM. The reproducibility of prediction was evaluated based on the correlation between the sets of U-test p-values on randomly divided datasets. With respect to leukemia, lymphoma and breast cancer, the correlation was high; a difference of >0.13 was obtained by the constructed model by using <50 genes selected by S2N'. Improvement was higher in the smaller genes and such higher correlation was observed when t-test, NSC and SAM were used. These results suggest that these modified methods, such as S2N', have high potential to function as new methods for marker gene selection in cancer diagnosis using DNA microarray data. AVAILABILITY: Software is available upon request.

Algorithms↗
PubMed2006

CAPS: coevolution analysis using protein sequences.

UNLABELLED: Coevolution Analysis using Protein Sequences (CAPS) is a PERL based software that identifies co-evolution between amino acid sites. Blosum-corrected amino acid distances are used to identify amino acid co-variation. The phylogenetic sequence relationships are used to remove the phylogenetic and stochastic dependencies between sites. The 3D protein structure is used to identify the nature of the dependencies between co-evolving amino acid sites. Friendly interpretable output files are generated. AVAILABILITY: CAPS version 1 is available at http://bioinf.gen.tcd.ie/~faresm/software/caps/. Distribution versions for Linux/Unix, Mac OS X and Windows operating systems are available, including manual and example files.

Algorithms↗
PubMed2006

Mosclust: a software library for discovering significant structures in bio-molecular data.

UNLABELLED: The R package mosclust (model order selection for clustering problems) implements algorithms based on the concept of stability for discovering significant structures in bio-molecular data. The software library provides stability indices obtained through different data perturbations methods (resampling, random projections, noise injection), as well as statistical tests to assess the significance of multi-level structures singled out from the data. AVAILABILITY: http://homes.dsi.unimi.it/~valenti/SW/mosclust/download/mosclust_1.0.tar.gz. SUPPLEMENTARY INFORMATION: http://homes.dsi.unimi.it/~valenti/SW/mosclust.

Algorithms↗
PubMed2006

Prophet, a web-based tool for class prediction using microarray data.

UNLABELLED: Sample classification and class prediction is the aim of many gene expression studies. We present a web-based application, Prophet, which builds prediction rules and allows using them for further sample classification. Prophet automatically chooses the best classifier, along with the optimal selection of genes, using a strategy that renders unbiased cross-validated errors. Prophet is linked to different microarray data analysis modules, and includes a unique feature: the possibility of performing the functional interpretation of the molecular signature found. AVAILABILITY: Prophet can be found at the URL http://prophet.bioinfo.cipf.es/ or within the GEPAS package at http://www.gepas.org/ SUPPLEMENTARY INFORMATION: http://gepas.bioinfo.cipf.es/tutorial/prophet.html.

Algorithms↗
PubMed2005

Building a tree of knowledge: analysis of bitter molecules.

A phylogenetic-like tree of structural fragments has been constructed to extract useful insights from a structural database of bitter molecules. The tree of structural fragments summarizes the substructural groups present in the molecules from the bitter database. These structural fragments are compared with a large number of random molecules to highlight substructures specific to bitter molecules. This organization of the structures enabled the detection of structure-activity relationships for the bitter molecules through the construction of R-tables. Key structural groups, able to distinguish between bitter and random molecules, were identified through an analysis of the tree. This information can be used to further understand which structural components are involved in producing a bitter taste.

Algorithms↗
PubMed2006

Neighbor-joining revealed.

It is nearly 20 years since the landmark paper (Saitou and Nei 1987) in Molecular Biology and Evolution introducing Neighbor-Joining (NJ). The method has become the most widely used method for building phylogenetic trees from distances, and the original paper has been cited about 13,000 times (Science Citation Index). Yet the question "what does the NJ method seek to do?" has until recently proved somewhat elusive, leading to some imprecise claims and misunderstanding. However, a rigorous answer to this question has recently been provided by further mathematical investigation, and the purpose of this note is to highlight these results and their significance for interpreting NJ. The origins of this story lie in a paper by Pauplin (2000) though its continuation has unfolded in more mathematically inclined literature. Our aim here is to make these findings more widely accessible.

Algorithms↗
PubMed2002

Identification of bladder wall layers by Raman spectroscopy.

PURPOSE: We explored the applicability of Raman spectroscopy to in situ investigation of bladder wall tissue. MATERIALS AND METHODS: Bladder wall tissue was obtained from a guinea pig model and frozen sections were used for Raman spectroscopic investigations. From each section 500 to 700 spectra were obtained in a 2-dimensional grid spanning the urothelium, lamina propria and muscle layer. The data set of spectra was subdivided into groups of similar spectra by a cluster analysis algorithm. With each group assigned a different color Raman maps of frozen sections were constructed based on group membership of measured spectra. These maps were then compared with histological and histochemical data obtained from hematoxylin and eosin and immunohistochemical staining for collagen I and III and for smooth muscle actin to correlate Raman spectral features with bladder wall structure and molecular composition. RESULTS: Urothelium, lamina propria and muscle layers could be clearly distinguished based on Raman spectra. Lamina propria spectra were dominated by signal contributions of collagen and the smooth muscle layer showed strong signal contributions of actin. The urothelium had a relatively strong lipid signal contribution. CONCLUSIONS: These results and the fact that Raman spectroscopy is rapidly evolving into a technology that can be applied in vivo by thin, flexible fiberoptic catheters indicate that prospects are good for in vivo analysis of the molecular composition of the normal and pathological bladder without biopsies.

Actins↗
PubMed2002

Role of pointlike topological excitations at criticality: From vortices to global monopoles.

We determine the detailed thermodynamic behavior of vortices in the O(2) scalar model in two dimensions (2D) and of global monopoles in the O(3) model in 3D. We construct numerical techniques, based on cluster decomposition algorithms, to analyze the point defect configurations. We find that these criteria produce results for the Kosterlitz-Thouless temperature in agreement with a topological transition between a polarizable insulator and a conductor, at which free topological charges appear in the system. For global monopoles we find no pair unbinding transition. Instead a transition to a dense state where pairs are no longer distinguishable occurs at T 3 are drawn, based on the observed behavior.

Journal Article↗
PubMed2004

WHEATSHEAF: an algorithm to average protein structure ensembles.

A new algorithm is described that forms a single structure representative of ensembles of structures from files in the format used by the Protein Data Bank. A first attempt is made by averaging in the space spanned by bond lengths, inter-bond rotations and symmetry-multiplied dihedral rotations. This normally produces well formed regular secondary-structure elements, but the intervening less well ordered regions are often distorted because of the invalidity of averaging large rotations about divergent axes. For this reason, the algorithm includes a second stage that pulls the interatomic distances towards more fully representative values. Results produced by this method have proved better as judged by conventional quality checks than any input structure in nearly all cases tested so far, especially for the backbone, and much better than those produced by commonly used alternative methods.

Algorithms↗
PubMed1996

Automatic identification of papillary muscles in left-ventricular short-axis echocardiographic images.

An automatic method for identifying the location of the papillary muscles in two-dimensional (2-D) short-axis echocardiographic images is described. The technique uses both spatial and temporal information to identify the presence and track the location of the muscles in the left ventricle from end-diastole to end-systole. The three main steps of the method are spatial preprocessing, spatial processing, and temporal processing. The spatial preprocessing step includes a region of search estimation. The spatial processing step includes a papillary muscle existence test and an initial approximation of the papillary muscle points. The temporal processing includes motion-pattern evaluation and final papillary muscle location. The estimates of existence and position for the automatic method were compared with estimates made by an independent expert observer. Two hundred and ten frames, three taken from each of 70 image sequences, were evaluated. Since two regions of search were processed for each frame (one for the posterior-inferior and one for the anterior-lateral papillary muscle), a total of 420 approximations were made. Of this total, 340 automatic estimates were judged to be in close agreement with estimates made by the expert. Of the remaining 80 approximations, 54 estimates were made by the expert when the computer determined that no papillary muscle was present, 17 estimates provided poor results, and nine estimates were made by the computer when the observer concluded that no papillary muscle was present.

Algorithms↗