In this paper, we propose a framework for unsupervised analysis of human behavior based on manifold learning. First, a pairwise human posture distance matrix is calculated from a training action sequence. Then, the isometric feature mapping (Isomap) algorithm is applied to construct a low-dimensional structure from the distance matrix. The data points in the Isomap space are consequently represented as a time-series of low-dimensional points. A temporal segmentation technique is then applied to segment the time series into subseries corresponding to atomic actions. Next, a dynamic time warping (DTW) approach is applied for clustering atomic action sequences. Finally, we use the clustering results to learn and classify atomic actions using the nearest neighbor rule. Experiments conducted on real data demonstrate the efficacy of the proposed method.

MOTIVATION: Homologous genomic sequences between species usually contain different rearrangement events. Whether some specific patterns existed in the breakpoint regions that caused such events to occur is still unclear. To resolve this question, it is necessary to determine the location of breakpoints at the nucleotide level. The availability of sequences near breakpoints would further facilitate the related studies. We thus need a tool that can identify breakpoints and align the neighboring sequences. Although local alignment tools can detect rearrangement events, they only report a set of discontinuous alignments, where the detailed alignments in the breakpoint regions are usually missing. Global alignment tools are even less appropriate for these tasks since most of them are designed to align the conserved regions between sequences in a consistent order, i.e. they do not consider rearrangement events. RESULTS: We propose an effective and efficient pairwise sequence alignment algorithm, called GR-Aligner (Genomic Rearrangement Aligner), which can find breakpoints of rearrangement events by integrating the forward and reverse alignments of the breakpoint regions flanked by homologously rearranged sequences. In addition, GR-Aligner also provides an option to view the alignments of sequences extended to the breakpoints. These outputs provide materials for studying possible evolutionary mechanisms and biological functionalities of the rearrangement.

Visual analysis of human behavior has generated considerable interest in the field of computer vision because of its wide spectrum of potential applications. Human behavior can be segmented into atomic actions, each of which indicates a basic and complete movement. Learning and recognizing atomic human actions are essential to human behavior analysis. In this paper, we propose a framework for handling this task using variable-length Markov models (VLMMs). The framework is comprised of the following two modules: a posture labeling module and a VLMM atomic action learning and recognition module. First, a posture template selection algorithm, based on a modified shape context matching technique, is developed. The selected posture templates form a codebook that is used to convert input posture sequences into discrete symbol sequences for subsequent processing. Then, the VLMM technique is applied to learn the training symbol sequences of atomic actions. Finally, the constructed VLMMs are transformed into hidden Markov models (HMMs) for recognizing input atomic actions. This approach combines the advantages of the excellent learning function of a VLMM and the fault-tolerant recognition ability of an HMM. Experiments on realistic data demonstrate the efficacy of the proposed system.

We propose a compact 3-D object representation scheme that can greatly assist the search/retrieval process in a network environment. A 3-D mesh-based object is transformed into a new coordinate frame by using the Isomap (isometric feature mapping) method. During the transformation process, not only the structure of the salient parts of an object will be kept, but also the geometrical relationships will be preserved. From the viewpoint of cognitive psychology, the data distributed on the Isomap manifold can be regarded as a set of significant features of a 3-D mesh-based object. To perform efficient matching, we project the Isomap domain 3-D object onto two different 2-D maps, and the two 2-D feature descriptors are used as the basis to measure the degree of similarity between two 3-D mesh-based objects. Experiments demonstrate that the proposed method in retrieving similar 3-D models is very effective. Most importantly, the proposed 3-D mesh retrieval scheme is still valid even if a 3-D mesh undergoes a mesh simplification process.

In this paper, we propose an automatic mesh decomposition technique based on principal component analysis (PCA) and Boolean operations. First, we calculate the normalized protrusion degree of each dual vertex on the smoothed 3-D mesh. The protrusion degree of a vertex and the vertex's 3-D coordinates form a 4-D feature vector, which we use to represent the polygon mesh. Since a 3-D object is composed of a large number of polygon meshes, we apply PCA to the set of 4-D feature vectors. We take the axes corresponding to the top three principal components as the three axes of a new coordinate system and project the set of 4-D vectors onto the system. Surprisingly, the projected data along the first axis reveals the salient structures of the 3-D object. Therefore, using the first component axis as the search basis, we can identify all the salient parts of an arbitrary 3-D object.

Visual analysis of human behavior has generated considerable interest in the field of computer vision because it has a wide spectrum of potential applications. Atomic human action recognition is an important part of a human behavior analysis system. In this paper, we propose a language modeling framework for this task. The framework is comprised of two modules: a posture labeling module, and an atomic action learning and recognition module. A posture template selection algorithm is developed based on a modified shape context matching technique. The posture templates form a codebook that is used to convert input posture sequences into training symbol sequences or recognition symbol sequences. Finally, a variable-length Markov model technique is applied to learn and recognize the input symbol sequences of atomic actions. Experiments on real data demonstrate the efficacy of the proposed system.

BACKGROUND: When aligning several hundreds or thousands of sequences, such as epidemic virus sequences or homologous/orthologous sequences of some big gene families, to reconstruct the epidemiological history or their phylogenies, how to analyze and visualize the alignment results of many sequences has become a new challenge for computational biologists. Although there are several tools available for visualization of very long sequence alignments, few of them are applicable to the alignments of many sequences. RESULTS: A multiple-logo alignment visualization tool, called Phylo-mLogo, is presented in this paper. Phylo-mLogo calculates the variabilities and homogeneities of alignment sequences by base frequencies or entropies. Different from the traditional representations of sequence logos, Phylo-mLogo not only displays the global logo patterns of the whole alignment of multiple sequences, but also demonstrates their local homologous logos for each clade hierarchically. In addition, Phylo-mLogo also allows the user to focus only on the analysis of some important, structurally or functionally constrained sites in the alignment selected by the user or by built-in automatic calculation. CONCLUSION: With Phylo-mLogo, the user can symbolically and hierarchically visualize hundreds of aligned sequences simultaneously and easily check the changes of their amino acid sites when analyzing many homologous/orthologous or influenza virus sequences. More information of Phylo-mLogo can be found at URL http://biocomp.iis.sinica.edu.tw/phylomlogo.

BACKGROUND: Deluged by the rate and complexity of completed genomic sequences, the need to align longer sequences becomes more urgent, and many more tools have thus been developed. In the initial stage of genomic sequence analysis, a biologist is usually faced with the questions of how to choose the best tool to align sequences of interest and how to analyze and visualize the alignment results, and then with the question of whether poorly aligned regions produced by the tool are indeed not homologous or are just results due to inappropriate alignment tools or scoring systems used. Although several systematic evaluations of multiple sequence alignment (MSA) programs have been proposed, they may not provide a standard-bearer for most biologists because those poorly aligned regions in these evaluations are never discussed. Thus, a tool that allows cross comparison of the alignment results obtained by different tools simultaneously could help a biologist evaluate their correctness and accuracy. RESULTS: In this paper, we present a versatile alignment visualization system, called SinicView, (for Sequence-aligning INnovative and Interactive Comparison VIEWer), which allows the user to efficiently compare and evaluate assorted nucleotide alignment results obtained by different tools. SinicView calculates similarity of the alignment outputs under a fixed window using the sum-of-pairs method and provides scoring profiles of each set of aligned sequences. The user can visually compare alignment results either in graphic scoring profiles or in plain text format of the aligned nucleotides along with the annotations information. We illustrate the capabilities of our visualization system by comparing alignment results obtained by MLAGAN, MAVID, and MULTIZ, respectively. CONCLUSION: With SinicView, users can use their own data sequences to compare various alignment tools or scoring systems and select the most suitable one to perform alignment in the initial stage of sequence analysis.

In this paper, we propose an iterated two-band filtering method to solve the selective image smoothing problem. We prove that a discrete computation step in an iterated nonlinear diffusion-based filtering algorithm is equivalent to a sequence of operations, including decomposition, regularization, and then reconstruction, in the proposed two-band filtering scheme. To correctly separate the high frequency components from the low frequency ones in the decomposition process, we adopt a dyadic wavelet-based approximation scheme. In the regularization process, we use a diffusivity function as a guide to retain useful data and suppress noises. Finally, the signal of the next stage, which is a "smoother" version of the signal at the previous stage, can be computed by reconstructing the decomposed low frequency component and the regularized high frequency component. Based on the proposed scheme, the smoothing operation can be applied to the correct targets. Experimental results show that our new approach is really efficient in noise removing.