Isomap transform for segmenting human body shapes

Segmentation of the 3D human body is a very challenging problem in applications exploiting volume capture data. Direct clustering in the Euclidean space is usually complex or even unsolvable. This paper presents an original method based on the Isomap (isometric feature mapping) transform of the volume data-set. The 3D articulated posture is mapped by Isomap in the pose of Da Vinci's Vitruvian man. The limbs are unrolled from each other and separated from the trunk and pelvis, and the topology of the human body shape is recovered. In such a configuration, Hoshen-Kopelman clustering applied to concentric spherical shells is used to automatically group points into the labelled principal curves. Shepard interpolation is utilised to back-map points of the principal curves into the original volume space. The experimental results performed on many different postures have proved the validity of the proposed method. Reliability of less than 2?cm and 3° in the location of the joint centres and direction axes of rotations has been obtained, respectively, which qualifies this procedure as a potential tool for markerless motion analysis.     

Multiple Manifold Clustering Using Curvature Constrained Path

The problem of multiple surface clustering is a challenging task, particularly when the surfaces intersect. Available methods such as Isomap fail to capture the true shape of the surface near by the intersection and result in incorrect clustering. The Isomap algorithm uses shortest path between points. The main draw back of the shortest path algorithm is due to the lack of curvature constrained where causes to have a path between points on different surfaces. In this paper we tackle this problem by imposing a curvature constraint to the shortest path algorithm used in Isomap. The algorithm chooses several landmark nodes at random and then checks whether there is a curvature constrained path between each landmark node and every other node in the neighborhood graph. We build a binary feature vector for each point where each entry represents the connectivity of that point to a particular landmark. Then the binary feature vectors could be used as a input of conventional clustering algorithm such as hierarchical clustering. We apply our method to simulated and some real datasets and show, it performs comparably to the best methods such as K-manifold and spectral multi-manifold clustering.     

Euclidean sections of protein conformation space and their implications in dimensionality reduction

Dimensionality reduction is widely used in searching for the intrinsic reaction coordinates for protein conformational changes. We find the dimensionality?reduction methods using the pairwise root?mean?square deviation (RMSD) as the local distance metric face a challenge. We use Isomap as an example to illustrate the problem. We believe that there is an implied assumption for the dimensionality‐reduction approaches that aim to preserve the geometric relations between the objects: both the original space and the reduced space have the same kind of geometry, such as Euclidean geometry vs. Euclidean geometry or spherical geometry vs. spherical geometry. When the protein free energy landscape is mapped onto a 2D plane or 3D space, the reduced space is Euclidean, thus the original space should also be Euclidean. For a protein with N atoms, its conformation space is a subset of the 3N‐dimensional Euclidean space R^3N. We formally define the protein conformation space as the quotient space of R^3N by the equivalence relation of rigid motions. Whether the quotient space is Euclidean or not depends on how it is parameterized. When the pairwise RMSD is employed as the local distance metric, implicit representations are used for the protein conformation space, leading to no direct correspondence to a Euclidean set. We have demonstrated that an explicit Euclidean‐based representation of protein conformation space and the local distance metric associated to it improve the quality of dimensionality reduction in the tetra‐peptide and β‐hairpin systems. Proteins 2014; 82:2585–2596. © 2014 Wiley Periodicals, Inc.     

Nonlinear dimensionality reduction: Alternative ordination approaches for extracting and visualizing biodiversity patterns in tropical montane forest vegetation data

Ecological patterns are difficult to extract directly from vegetation data. The respective surveys provide a high number of interrelated species occurrence variables. Since often only a limited number of ecological gradients determine species distributions, the data might be represented by much fewer but effectively independent variables. This can be achieved by reducing the dimensionality of the data. Conventional methods are either limited to linear feature extraction (e.g., principal component analysis, and Classical Multidimensional Scaling, CMDS) or require a priori assumptions on the intrinsic data dimensionality (e.g., Nonmetric Multidimensional Scaling, NMDS, and self organized maps, SOM).In this study we explored the potential of Isometric Feature Mapping (Isomap). This new method of dimensionality reduction is a nonlinear generalization of CMDS. Isomap is based on a nonlinear geodesic inter-point distance matrix. Estimating geodesic distances requires one free threshold parameter, which defines linear geometry to be preserved in the global nonlinear distance structure. We compared Isomap to its linear (CMDS) and nonmetric (NMDS) equivalents. Furthermore, the use of geodesic distances allowed also extending NMDS to a version that we called NMDS-G. In addition we investigated a supervised Isomap variant (S-Isomap) and showed that all these techniques are interpretable within a single methodical framework.As an example we investigated seven plots (subdivided in 456 subplots) in different secondary tropical montane forests with 773 species of vascular plants. A key problem for the study of tropical vegetation data is the heterogeneous small scale variability implying large ranges of β-diversity. The CMDS and NMDS methods did not reduce the data dimensionality reasonably. On the contrary, Isomap explained 95% of the data variance in the first five dimensions and provided ecologically interpretable visualizations; NMDS-G yielded similar results. The main shortcoming of the latter was the high computational cost and the requirement to predefine the dimension of the embedding space. The S-Isomap learning scheme did not improve the Isomap variant for an optimal threshold parameter but substantially improved the nonoptimal solutions.We conclude that Isomap as a new ordination method allows effective representations of high dimensional vegetation data sets. The method is promising since it does not require a priori assumptions, and is computationally highly effective.     

Revealing biogeographical patterns by nonlinear ordinations and derived anisotropic spatial filters

Aim Spatial floristic and faunistic data bases promote the investigation of biogeographical gradients in relation to environmental determinants on regional to continental scales. Our aim was to extract major gradients in the distribution of vascular plant species from a grid‐based inventory (the German FLORKART data base) and relate them to long‐term precipitation and temperature records as well as soil conditions. We present an ordination technique capable of coping with this complex data array. The goal was also to sort out the influence of spatial autocorrelation, assuming floristic autocorrelation is anisotropic. Location Germany, at a spatial resolution of 6′ × 10′. Methods Isometric feature mapping (Isomap) was applied as a nonlinear ordination method. Isomap was coupled to ‘eigenvector‐based filters’ for generating spatial reference models representing spatial autocorrelation. What is novel here is that the derived filters are not based on the assumption of equidirectional autocorrelation. Instead, the so‐called ‘principal coordinates of anisotropic neighbour matrices’ build filters to test the influence of geographical vicinity in directions of high similarity among observations. Results The Isomap ordination of floristic data explained more than 95% of the data variance in six dimensions. The leading two dimensions (representing about 80% of the FLORKART data variance) revealed clear spatial gradients that could be related to independent effects of temperature, precipitation and soil observations. By contrast, the third and higher FLORKART dimensions were dominated by an antagonism of anisotropic spatial autocorrelation and soil conditions. A subsequent cluster analysis of the floristic Isomap coordinates educed the spatial organization of the floristic survey, indicating a considerable sampling bias. Conclusions We showed that Isomap provides a consistent methodical framework for both ordination and derived spatial filters. The technique is useful for tracing the often nonlinear features of species occurrence data to environmental drivers, taking into account anisotropic spatial autocorrelation. We also showed that sampling biases are a conspicuous source of variance in a frequently used floristic data base.     

From spatial-data to 3D models of the developing human brain

Visualisation and interpretation of gene expression data have been crucial to advances in our understanding of mechanisms underlying early brain development. As most developmental processes involve complex changes in size, shape and structure, spatial-data can most readily provide information at multiple levels (cell type, cell location in relation to tissue organisation or body axes, etc.), that can be related to these complex changes. Although three-dimensional (3D) spatial-data are ideal, the restricted availability of suitable tissues makes it difficult to generate these for genes expressed at early human fetal stages. Mapping gene expression data to representative 3D models facilitates combinatorial analysis of multiple expression patterns but does not overcome the problems of sparsely sampled data in time and space. Here we describe software that allows 3D domains to be reconstructed by interpolating between sparse 2D gene expression patterns that have been mapped to 3D representative models of corresponding human developmental stages. A set of procedures are proposed to infer expression domains in these gaps. The procedures, which are connected in a serial way, include components clustering, components tracking, shape matching and points interpolation. Each procedure consists of a graphical user interface and a set of algorithms. Results on exemplar gene data are provided.     

CT-based semi-automatic quantification of vertebral fracture restoration

Minimally invasive surgeries aiming to restore fractured vertebral body are increasing; therefore, our goals were to create a 3D vertebra reconstruction process and design clinical indices to assess the vertebral restoration in terms of heights, angles and volumes. Based on computed tomography (CT)-scan of the vertebral spine, a 3D reconstruction method as well as relevant clinical indices were developed. First, a vertebra initial solution requiring 5 min of manual adjustments is built. Then an image processing algorithm places this solution in the CT-scan images volume to adjust the model's nodes. On the vertebral body's anterior and posterior parts, nine robust heights, volume and endplate angle measurement methods were developed. These parameters were evaluated by reproducibility and accuracy studies. The vertebral body reconstruction accuracy was 1.0 mm; heights and volume accuracy were, respectively, 1.2 and 179 mm³. In conclusion, a 3D vertebra reconstruction process requiring little user time was proposed as well as 3D clinical indices assessing fractured and restored vertebra.     

Approximate geodesic distances reveal biologically relevant structures in microarray data

MOTIVATION: Genome-wide gene expression measurements, as currently determined by the microarray technology, can be represented mathematically as points in a high-dimensional gene expression space. Genes interact with each other in regulatory networks, restricting the cellular gene expression profiles to a certain manifold, or surface, in gene expression space. To obtain knowledge about this manifold, various dimensionality reduction methods and distance metrics are used. For data points distributed on curved manifolds, a sensible distance measure would be the geodesic distance along the manifold. In this work, we examine whether an approximate geodesic distance measure captures biological similarities better than the traditionally used Euclidean distance. RESULTS: We computed approximate geodesic distances, determined by the Isomap algorithm, for one set of lymphoma and one set of lung cancer microarray samples. Compared with the ordinary Euclidean distance metric, this distance measure produced more instructive, biologically relevant, visualizations when applying multidimensional scaling. This suggests the Isomap algorithm as a promising tool for the interpretation of microarray data. Furthermore, the results demonstrate the benefit and importance of taking nonlinearities in gene expression data into account.     

Clustering Time-Series Gene Expression Data Using Smoothing Spline Derivatives

Microarray data acquired during time-course experiments allow the temporal variations in gene expression to be monitored. An original postprandial fasting experiment was conducted in the mouse and the expression of 200 genes was monitored with a dedicated macroarray at 11 time points between 0 and 72 hours of fasting. The aim of this study was to provide a relevant clustering of gene expression temporal profiles. This was achieved by focusing on the shapes of the curves rather than on the absolute level of expression. Actually, we combined spline smoothing and first derivative computation with hierarchical and partitioning clustering. A heuristic approach was proposed to tune the spline smoothing parameter using both statistical and biological considerations. Clusters are illustrated a posteriori through principal component analysis and heatmap visualization. Most results were found to be in agreement with the literature on the effects of fasting on the mouse liver and provide promising directions for future biological investigations.     

Geometric versus topological clustering: An insight into conformation mapping

Clustering molecular conformations into “families” is a common procedure in conformational analysis of molecular systems. An implicit assumption which often underlies this clustering approach is that the resulting geometric families reflect the energetic structure of the system's potential energy surface. In a broader context we address the question whether structural similarity is correlated with energy basins, i.e., whether conformations that belong to the same energy basin are also geometrically similar. “Topological mapping” and principal coordinate projections are used here to address this question and to assess the quality of the “family clustering” procedure. Applying the analysis to a small tetrapeptide it was found that the general correlation that exists between energy basins and structural similarity is not absolute. Clusters generated by the geometric “family clustering” procedure do not always reflect the underlying energy basins. In particular it was found that the “family tree” that is generated by the “family clustering” procedure is completely inconsistent with its real topological counterpart, the “disconnectivity” graph of this system. It is also demonstrated that principal coordinate analysis is a powerful visualization technique which, at least for this system, works better when distances are measured in dihedral angle space rather than in cartesian space. © 1997 Wiley-Liss, Inc.     

A New Method for the Analysis of Soft Tissues with Data Acquired under Field Conditions

Analyzing soft-tissue structures is particularly challenging due to the lack of homologous landmarks that can be reliably identified across time and specimens. This is particularly true when data are to be collected under field conditions. Here, we present a method that combines photogrammetric techniques and geometric morphometrics methods (GMM) to quantify soft tissues for their subsequent volumetric analysis. We combine previously developed methods for landmark data acquisition and processing with a custom program for volumetric computations. Photogrammetric methods are a particularly powerful tool for field studies as they allow for image acquisition with minimal equipment requirements and for the acquisition of the spatial coordinates of points (anatomical landmarks or others) from these images. For our method, a limited number of homologous landmarks, i.e., points that can be found on any specimen independent of space and time, and further distinctive points, which may vary over time, space and subject, are identified on two-dimensional photographs and their three-dimensional coordinates estimated using photogrammetric methods. The three-dimensional configurations are oriented by the spatial principal components (PCs) of the homologous points. Crucially, this last step orients the configuration such that x and y-information (PC1 and PC2 coordinates) constitute an anatomically-defined plane with the z-values (PC3 coordinate) in the direction of interest for volume computation. The z-coordinates are then used to estimate the volume of the tissue. We validate our method using a physical, geometric model of known dimensions and physical (wax) models designed to approximate perineal swellings in female macaques. To demonstrate the usefulness and potential of our method, we use it to estimate the volumes of Barbary macaque sexual swellings recorded in the field with video images. By analyzing both the artificial data and real monkey swellings, we validate our method''s accuracy and illustrate its potential for application in important areas of biological research.     

Biview Learning for Human Posture Segmentation from 3D Points Cloud

Posture segmentation plays an essential role in human motion analysis. The state-of-the-art method extracts sufficiently high-dimensional features from 3D depth images for each 3D point and learns an efficient body part classifier. However, high-dimensional features are memory-consuming and difficult to handle on large-scale training dataset. In this paper, we propose an efficient two-stage dimension reduction scheme, termed biview learning, to encode two independent views which are depth-difference features (DDF) and relative position features (RPF). Biview learning explores the complementary property of DDF and RPF, and uses two stages to learn a compact yet comprehensive low-dimensional feature space for posture segmentation. In the first stage, discriminative locality alignment (DLA) is applied to the high-dimensional DDF to learn a discriminative low-dimensional representation. In the second stage, canonical correlation analysis (CCA) is used to explore the complementary property of RPF and the dimensionality reduced DDF. Finally, we train a support vector machine (SVM) over the output of CCA. We carefully validate the effectiveness of DLA and CCA utilized in the two-stage scheme on our 3D human points cloud dataset. Experimental results show that the proposed biview learning scheme significantly outperforms the state-of-the-art method for human posture segmentation.     

On the distinctness of clusters

A common problem in classification is the assignment of objects to meaningful clusters given their relative positions in reduced ordination space. We examine the distinctiveness of such putative clusters.Clusters are enlarged by simulation and then the relative frequency distributions of interpoint distances in the “enlarged” clusters are compared with the distribution of the original points in the original space. This procedure may be repeated for all reasonable clustering hypotheses until the best fit is found.We suggest that one way of looking at the distinctness of clusters is to look at the distribution of interpoint distances for various hypothetical clusters from which the data might have been sampled. The best clustering, given the data, is the one that best matches the original distribution of interpoint distances.     

A combination dimensionality reduction approach to codon position patterns of eubacteria based on their complete genomes

Graphical techniques have become powerful tools for the visualization and analysis of complicated biological systems. However, we cannot give such a graphical representation in a 2D/3D space when the dimensions of the represented data are more than three dimensions. The proposed method, a combination dimensionality reduction approach (CDR), consists of two parts: (i) principal component analysis (PCA) with a newly defined parameter ρ and (ii) locally linear embedding (LLE) with a proposed graphical selection for its optional parameter k. The CDR approach with ρ and k not only avoids loss of principal information, but also sufficiently well preserves the global high-dimensional structures in low-dimensional space such as 2D or 3D. The applications of the CDR on characteristic analysis at different codon positions in genome show that the method is a useful tool by which biologists could find useful biological knowledge.     

离子通道亚型与其基因共表达的关联研究

离子通道亚型与其基因共表达的关联对研究离子通道功能有重要意义。文章采用主成分分析和模糊C-均值聚类算法对数据进行分析, 将方法应用到人类和小鼠两套表达谱数据, 结果发现离子通道亚型中钾离子通道、钙离子通道、氯离子通道和受体激活型离子通道的表达谱聚类结果与生物学分类有较好的一致性, 体现了离子通道亚型在mRNA水平上的共表达, 并证实了通过离子通道表达谱能很好的对离子通道的功能亚型进行分类。     

Edge Principal Components and Squash Clustering: Using the Special Structure of Phylogenetic Placement Data for Sample Comparison

Principal components analysis (PCA) and hierarchical clustering are two of the most heavily used techniques for analyzing the differences between nucleic acid sequence samples taken from a given environment. They have led to many insights regarding the structure of microbial communities. We have developed two new complementary methods that leverage how this microbial community data sits on a phylogenetic tree. Edge principal components analysis enables the detection of important differences between samples that contain closely related taxa. Each principal component axis is a collection of signed weights on the edges of the phylogenetic tree, and these weights are easily visualized by a suitable thickening and coloring of the edges. Squash clustering outputs a (rooted) clustering tree in which each internal node corresponds to an appropriate “average” of the original samples at the leaves below the node. Moreover, the length of an edge is a suitably defined distance between the averaged samples associated with the two incident nodes, rather than the less interpretable average of distances produced by UPGMA, the most widely used hierarchical clustering method in this context. We present these methods and illustrate their use with data from the human microbiome.     

Uptake of 36Cl and 22Na by the Brain-Cerebrospinal Fluid System: Comparison of the Permeability of the Blood-Brain and Blood-Cerebrospinal Fluid Barriers

Abstract: Transport and permeability properties of the blood-brain and blood-CSF barriers were determined by kinetic analysis of radioisotope uptake from the plasma into the CNS of the adult rat. Cerebral cortex and cerebellum uptake curves for ³⁶Cl and ²²Na were resolved into two components. The fast component (t_½ 0.02–0.05 h, fractional volume 0.04–0.08) is comprised of the vascular compartment and a small perivascular space whereas the slow component (t_½ 1.06–1.69 h, fractional volume 0.92–0.96) represents isotope movement across the blood-brain barrier into the brain extracellular and cellular compartments. Uptake curves of both ³⁶Cl and ²²Na into the CSF were also resolved into two components, a fast component (t_½ 0.18 h, fractional volume 0.24) and a slow component (t_½ 1.2 h, fractional volume 0.76). Evidence suggests that the fast component represents isotope movement across the blood-CSF barrier, i.e., the choroid plexuses, whereas the CSF slow component probably reflects isotope penetration primarily from the brain extracellular fluid into the CSF. The extracellular fluid volume of the cerebral cortex and cerebellum was estimated as ?13% from the initial slope of the curve of brain space versus CSF space curve for both ³⁶Cl and ²²Na. Like the choroid plexuses, the glial cell compartment of the brain appears to accumulate Cl from 2 to 6 times that predicted for passive distribution. The relative permeability of the blood-CSF and blood-brain barriers to ³⁶Cl, ²²Na, and [³H]mannitol was determined by calculating permeability surface-area products (PA). Analysis of the PA values for all three isotopes indicates that the effective permeability of the choroidal epithelium (blood/CSF barrier) is significantly greater than that of the capillary endothelium in the cerebral cortex and cerebellum (blood-brain barrier).     

Link Clustering with Extended Link Similarity and EQ Evaluation Division

Link Clustering (LC) is a relatively new method for detecting overlapping communities in networks. The basic principle of LC is to derive a transform matrix whose elements are composed of the link similarity of neighbor links based on the Jaccard distance calculation; then it applies hierarchical clustering to the transform matrix and uses a measure of partition density on the resulting dendrogram to determine the cut level for best community detection. However, the original link clustering method does not consider the link similarity of non-neighbor links, and the partition density tends to divide the communities into many small communities. In this paper, an Extended Link Clustering method (ELC) for overlapping community detection is proposed. The improved method employs a new link similarity, Extended Link Similarity (ELS), to produce a denser transform matrix, and uses the maximum value of EQ (an extended measure of quality of modularity) as a means to optimally cut the dendrogram for better partitioning of the original network space. Since ELS uses more link information, the resulting transform matrix provides a superior basis for clustering and analysis. Further, using the EQ value to find the best level for the hierarchical clustering dendrogram division, we obtain communities that are more sensible and reasonable than the ones obtained by the partition density evaluation. Experimentation on five real-world networks and artificially-generated networks shows that the ELC method achieves higher EQ and In-group Proportion (IGP) values. Additionally, communities are more realistic than those generated by either of the original LC method or the classical CPM method.