Developmental genetics and homology: a hierarchical approach

New advances in developmental genetics are providing a bridge to connect the study of development and evolution. The successful integration of these fields, however, is dependent on having a clear understanding of the concept of homology. Therefore, developmental genetic data must be placed within the context of the comparative method to provide insight into the evolutionary and developmental origins of traits. The comparative analysis of traits derived from several hierarchical levels (genes, gene expression patterns, embryonic origins and morphology) can potentially reveal scenarios of developmental integration, opportunity and constraint. Moreover, this approach has implications for resolving modern controversies surrounding the concept of homology.     

HCPM--program for hierarchical clustering of protein models

HCPM is a tool for clustering protein structures from comparative modeling, ab initio structure prediction, etc. A hierarchical clustering algorithm is designed and tested, and a heuristic is provided for an optimal cluster selection. The method has been successfully tested during the CASP6 experiment.     

Large scale hierarchical clustering of protein sequences

Background  

Searching a biological sequence database with a query sequence looking for homologues has become a routine operation in computational biology. In spite of the high degree of sophistication of currently available search routines it is still virtually impossible to identify quickly and clearly a group of sequences that a given query sequence belongs to.     

Class-specific correlations of gene expressions: identification and their effects on clustering analyses

Current microarray studies primarily focus on identifying individual genes with differential expression levels across different conditions or classes. A potential problem is that they may disregard multidimensional information hidden in gene interactions. In this study, we propose an approach to detect gene interactions related to study phenotypes through identifying gene pairs with correlations that appear to be class or condition specific. In addition, we explore the effects of ignoring class-specific correlations (CSC) on correlation-based gene-clustering analyses. Our simulation studies show that ignoring CSC can significantly decrease the accuracy of gene clustering and increase the dissimilarity within clusters. Our results from a DLBCL (distinct types of diffuse large B cell lymphoma) data set illustrate that CSC are clearly present and have great adverse effects on gene-clustering results if ignored. Meanwhile, interesting biological interpretations may be derived from studying gene pairs with CSC. This study demonstrates that our algorithm is simple and computationally efficient and has the ability to detect gene pairs with CSC that are informative for uncovering interesting regulation patterns.     

Semi-supervised adaptive-height snipping of the hierarchical clustering tree

Background

In genomics, hierarchical clustering (HC) is a popular method for grouping similar samples based on a distance measure. HC algorithms do not actually create clusters, but compute a hierarchical representation of the data set. Usually, a fixed height on the HC tree is used, and each contiguous branch of samples below that height is considered a separate cluster. Due to the fixed-height cutting, those clusters may not unravel significant functional coherence hidden deeper in the tree. Besides that, most existing approaches do not make use of available clinical information to guide cluster extraction from the HC. Thus, the identified subgroups may be difficult to interpret in relation to that information.

Results

We develop a novel framework for decomposing the HC tree into clusters by semi-supervised piecewise snipping. The framework, called guided piecewise snipping, utilizes both molecular data and clinical information to decompose the HC tree into clusters. It cuts the given HC tree at variable heights to find a partition (a set of non-overlapping clusters) which does not only represent a structure deemed to underlie the data from which HC tree is derived, but is also maximally consistent with the supplied clinical data. Moreover, the approach does not require the user to specify the number of clusters prior to the analysis. Extensive results on simulated and multiple medical data sets show that our approach consistently produces more meaningful clusters than the standard fixed-height cut and/or non-guided approaches.

Conclusions

The guided piecewise snipping approach features several novelties and advantages over existing approaches. The proposed algorithm is generic, and can be combined with other algorithms that operate on detected clusters. This approach represents an advancement in several regards: (1) a piecewise tree snipping framework that efficiently extracts clusters by snipping the HC tree possibly at variable heights while preserving the HC tree structure; (2) a flexible implementation allowing a variety of data types for both building and snipping the HC tree, including patient follow-up data like survival as auxiliary information.The data sets and R code are provided as supplementary files. The proposed method is available from Bioconductor as the R-package HCsnip.

Electronic supplementary material

The online version of this article (doi:10.1186/s12859-014-0448-1) contains supplementary material, which is available to authorized users.     

Inferring population structure and relationship using minimal independent evolutionary markers in Y-chromosome: a hybrid approach of recursive feature selection for hierarchical clustering

Inundation of evolutionary markers expedited in Human Genome Project and 1000 Genome Consortium has necessitated pruning of redundant and dependent variables. Various computational tools based on machine-learning and data-mining methods like feature selection/extraction have been proposed to escape the curse of dimensionality in large datasets. Incidentally, evolutionary studies, primarily based on sequentially evolved variations have remained un-facilitated by such advances till date. Here, we present a novel approach of recursive feature selection for hierarchical clustering of Y-chromosomal SNPs/haplogroups to select a minimal set of independent markers, sufficient to infer population structure as precisely as deduced by a larger number of evolutionary markers. To validate the applicability of our approach, we optimally designed MALDI-TOF mass spectrometry-based multiplex to accommodate independent Y-chromosomal markers in a single multiplex and genotyped two geographically distinct Indian populations. An analysis of 105 world-wide populations reflected that 15 independent variations/markers were optimal in defining population structure parameters, such as F_ST, molecular variance and correlation-based relationship. A subsequent addition of randomly selected markers had a negligible effect (close to zero, i.e. 1 × 10⁻³) on these parameters. The study proves efficient in tracing complex population structures and deriving relationships among world-wide populations in a cost-effective and expedient manner.     

R/BHC: fast Bayesian hierarchical clustering for microarray data

Background  

Although the use of clustering methods has rapidly become one of the standard computational approaches in the literature of microarray gene expression data analysis, little attention has been paid to uncertainty in the results obtained.     

CLUSTAG: hierarchical clustering and graph methods for selecting tag SNPs

SUMMARY: Cluster and set-cover algorithms are developed to obtain a set of tag single nucleotide polymorphisms (SNPs) that can represent all the known SNPs in a chromosomal region, subject to the constraint that all SNPs must have a squared correlation R2>C with at least one tag SNP, where C is specified by the user. AVAILABILITY: http://hkumath.hku.hk/web/link/CLUSTAG/CLUSTAG.html CONTACT: mng@maths.hku.hk.     

A memetic-aided approach to hierarchical clustering from distance matrices: application to gene expression clustering and phylogeny

We propose a heuristic approach to hierarchical clustering from distance matrices based on the use of memetic algorithms (MAs). By using MAs to solve some variants of the Minimum Weight Hamiltonian Path Problem on the input matrix, a sequence of the individual elements to be clustered (referred to as patterns) is first obtained. While this problem is also NP-hard, a probably optimal sequence is easy to find with the current advances for this problem and helps to prune the space of possible solutions and/or to guide the search performed by an actual clustering algorithm. This technique has been successfully applied to both a Branch-and-Bound algorithm, and to evolutionary algorithms and MAs. Experimental results are given in the context of phylogenetic inference and in the hierarchical clustering of gene expression data.     

A hierarchical method for finding optimal architecture and weights using evolutionary least square based learning

In this paper, we present a novel approach of implementing a combination methodology to find appropriate neural network architecture and weights using an evolutionary least square based algorithm (GALS).1 This paper focuses on aspects such as the heuristics of updating weights using an evolutionary least square based algorithm, finding the number of hidden neurons for a two layer feed forward neural network, the stopping criterion for the algorithm and finally some comparisons of the results with other existing methods for searching optimal or near optimal solution in the multidimensional complex search space comprising the architecture and the weight variables. We explain how the weight updating algorithm using evolutionary least square based approach can be combined with the growing architecture model to find the optimum number of hidden neurons. We also discuss the issues of finding a probabilistic solution space as a starting point for the least square method and address the problems involving fitness breaking. We apply the proposed approach to XOR problem, 10 bit odd parity problem and many real-world benchmark data sets such as handwriting data set from CEDAR, breast cancer and heart disease data sets from UCI ML repository. The comparative results based on classification accuracy and the time complexity are discussed.     

Cryptic organelle homology in apicomplexan parasites: insights from evolutionary cell biology

1. Download : Download high-res image (188KB)
2. Download : Download full-size image

     

Pvclust: an R package for assessing the uncertainty in hierarchical clustering

SUMMARY: Pvclust is an add-on package for a statistical software R to assess the uncertainty in hierarchical cluster analysis. Pvclust can be used easily for general statistical problems, such as DNA microarray analysis, to perform the bootstrap analysis of clustering, which has been popular in phylogenetic analysis. Pvclust calculates probability values (p-values) for each cluster using bootstrap resampling techniques. Two types of p-values are available: approximately unbiased (AU) p-value and bootstrap probability (BP) value. Multiscale bootstrap resampling is used for the calculation of AU p-value, which has superiority in bias over BP value calculated by the ordinary bootstrap resampling. In addition the computation time can be enormously decreased with parallel computing option.     

TBC: A clustering algorithm based on prokaryotic taxonomy

High-throughput DNA sequencing technologies have revolutionized the study of microbial ecology. Massive sequencing of PCR amplicons of the 16S rRNA gene has been widely used to understand the microbial community structure of a variety of environmental samples. The resulting sequencing reads are clustered into operational taxonomic units that are then used to calculate various statistical indices that represent the degree of species diversity in a given sample. Several algorithms have been developed to perform this task, but they tend to produce different outcomes. Herein, we propose a novel sequence clustering algorithm, namely Taxonomy-Based Clustering (TBC). This algorithm incorporates the basic concept of prokaryotic taxonomy in which only comparisons to the type strain are made and used to form species while omitting full-scale multiple sequence alignment. The clustering quality of the proposed method was compared with those of MOTHUR, BLASTClust, ESPRIT-Tree, CD-HIT, and UCLUST. A comprehensive comparison using three different experimental datasets produced by pyrosequencing demonstrated that the clustering obtained using TBC is comparable to those obtained using MOTHUR and ESPRIT-Tree and is computationally efficient. The program was written in JAVA and is available from .     

Inevitable evolutionary temporal elements in neural processing: a study based on evolutionary simulations

Recent studies have suggested that some neural computational mechanisms are based on the fine temporal structure of spiking activity. However, less effort has been devoted to investigating the evolutionary aspects of such mechanisms. In this paper we explore the issue of temporal neural computation from an evolutionary point of view, using a genetic simulation of the evolutionary development of neural systems. We evolve neural systems in an environment with selective pressure based on mate finding, and examine the temporal aspects of the evolved systems. In repeating evolutionary sessions, there was a significant increase during evolution in the mutual information between the evolved agent's temporal neural representation and the external environment. In ten different simulated evolutionary sessions, there was an increased effect of time-related neural ablations on the agents' fitness. These results suggest that in some fitness landscapes the emergence of temporal elements in neural computation is almost inevitable. Future research using similar evolutionary simulations may shed new light on various biological mechanisms.     

Facial attractiveness: evolutionary based research

Face preferences affect a diverse range of critical social outcomes, from mate choices and decisions about platonic relationships to hiring decisions and decisions about social exchange. Firstly, we review the facial characteristics that influence attractiveness judgements of faces (e.g. symmetry, sexually dimorphic shape cues, averageness, skin colour/texture and cues to personality) and then review several important sources of individual differences in face preferences (e.g. hormone levels and fertility, own attractiveness and personality, visual experience, familiarity and imprinting, social learning). The research relating to these issues highlights flexible, sophisticated systems that support and promote adaptive responses to faces that appear to function to maximize the benefits of both our mate choices and more general decisions about other types of social partners.