Analysis and implementation of a neural extended Kalman filter for target tracking

Having a better motion model in the state estimator is one way to improve target tracking performance. Since the motion model of the target is not known a priori, either robust modeling techniques or adaptive modeling techniques are required. The neural extended Kalman filter is a technique that learns unmodeled dynamics while performing state estimation in the feedback loop of a control system. This coupled system performs the standard estimation of the states of the plant while estimating a function to approximate the difference between the given state-coupling function model and the behavior of the true plant dynamics. At each sample step, this new model is added to the existing model to improve the state estimate. The neural extended Kalman filter has also been investigated as a target tracking estimation routine. Implementation issues for this adaptive modeling technique, including neural network training parameters, were investigated and an analysis was made of the quality of performance that the technique can have for tracking maneuvering targets.     

Optimal Appearance Model for Visual Tracking

Many studies argue that integrating multiple cues in an adaptive way increases tracking performance. However, what is the definition of adaptiveness and how to realize it remains an open issue. On the premise that the model with optimal discriminative ability is also optimal for tracking the target, this work realizes adaptiveness and robustness through the optimization of multi-cue integration models. Specifically, based on prior knowledge and current observation, a set of discrete samples are generated to approximate the foreground and background distribution. With the goal of optimizing the classification margin, an objective function is defined, and the appearance model is optimized by introducing optimization algorithms. The proposed optimized appearance model framework is embedded into a particle filter for a field test, and it is demonstrated to be robust against various kinds of complex tracking conditions. This model is general and can be easily extended to other parameterized multi-cue models.     

Phylogenetic relationships and heterogeneous evolutionary processes among phrynosomatine sand lizards (Squamata, Iguanidae) revisited

Phylogenetic analyses of DNA sequences were conducted to evaluate four alternative hypotheses of phrynosomatine sand lizard relationships. Sequences comprising 2871 aligned base pair positions representing the regions spanning ND1-COI and cyt b-tRNA(Thr) of the mitochondrial genome from all recognized sand lizard species were analyzed using unpartitioned parsimony and likelihood methods, likelihood methods with assumed partitions, Bayesian methods with assumed partitions, and Bayesian mixture models. The topology (Uma, (Callisaurus, (Cophosaurus, Holbrookia))) and thus monophyly of the "earless" taxa, Cophosaurus and Holbrookia, is supported by all analyses. Previously proposed topologies in which Uma and Callisaurus are sister taxa and those in which Holbrookia is the sister group to all other sand lizard taxa are rejected using both parsimony and likelihood-based significance tests with the combined, unparitioned data set. Bayesian hypothesis tests also reject those topologies using six assumed partitioning strategies, and the two partitioning strategies presumably associated with the most powerful tests also reject a third previously proposed topology, in which Callisaurus and Cophosaurus are sister taxa. For both maximum likelihood and Bayesian methods with assumed partitions, those partitions defined by codon position and tRNA stem and nonstems explained the data better than other strategies examined. Bayes factor estimates comparing results of assumed partitions versus mixture models suggest that mixture models perform better than assumed partitions when the latter were not based on functional characteristics of the data, such as codon position and tRNA stem and nonstems. However, assumed partitions performed better than mixture models when functional differences were incorporated. We reiterate the importance of accounting for heterogeneous evolutionary processes in the analysis of complex data sets and emphasize the importance of implementing mixed model likelihood methods.     

Protein multi-scale organization through graph partitioning and robustness analysis: application to the myosin-myosin light chain interaction

Despite the recognized importance of the multi-scale spatio-temporal organization of proteins, most computational tools can only access a limited spectrum of time and spatial scales, thereby ignoring the effects on protein behavior of the intricate coupling between the different scales. Starting from a physico-chemical atomistic network of interactions that encodes the structure of the protein, we introduce a methodology based on multi-scale graph partitioning that can uncover partitions and levels of organization of proteins that span the whole range of scales, revealing biological features occurring at different levels of organization and tracking their effect across scales. Additionally, we introduce a measure of robustness to quantify the relevance of the partitions through the generation of biochemically-motivated surrogate random graph models. We apply the method to four distinct conformations of myosin tail interacting protein, a protein from the molecular motor of the malaria parasite, and study properties that have been experimentally addressed such as the closing mechanism, the presence of conserved clusters, and the identification through computational mutational analysis of key residues for binding.     

The k partition-distance problem

Many applications of data partitioning (clustering) have been well studied in bioinformatics. Consider, for instance, a set N of organisms (elements) based on DNA marker data. A partition divides all elements in N into two or more disjoint clusters that cover all elements, where a cluster contains a non-empty subset of N. Different partitioning algorithms may produce different partitions. To compute the distance and find the consensus partition (also called consensus clustering) between two or more partitions are important and interesting problems that arise frequently in bioinformatics and data mining, in which different distance functions may be considered in different partition algorithms. In this article, we discuss the k partition-distance problem. Given a set of elements N with k partitions of N, the k partition-distance problem is to delete the minimum number of elements from each partition such that all remaining partitions become identical. This problem is NP-complete for general k?>?2 partitions, and no algorithms are known at present. We design the first known heuristic and approximation algorithms with performance ratios 2 to solve the k partition-distance problem in O(k?·?ρ?·?|N|) time, where ρ is the maximum number of clusters of these k partitions and |N| is the number of elements in N. We also present the first known exact algorithm in O(??·?2(?)·k(2)?·?|N|(2)) time, where ? is the partition-distance of the optimal solution for this problem. Performances of our exact and approximation algorithms in testing the random data with actual sets of organisms based on DNA markers are compared and discussed. Experimental results reveal that our algorithms can improve the computational speed of the exact algorithm for the two partition-distance problem in practice if the maximum number of elements per cluster is less than ρ. From both theoretical and computational points of view, our solutions are at most twice the partition-distance of the optimal solution. A website offering the interactive service of solving the k partition-distance problem using our and previous algorithms is available (see http://mail.tmue.edu.tw/~yhchen/KPDP.html).     

Partitioned Bayesian analyses, partition choice, and the phylogenetic relationships of scincid lizards

Partitioned Bayesian analyses of approximately 2.2 kb of nucleotide sequence data (mtDNA) were used to elucidate phylogenetic relationships among 30 scincid lizard genera. Few partitioned Bayesian analyses exist in the literature, resulting in a lack of methods to determine the appropriate number of and identity of partitions. Thus, a criterion, based on the Bayes factor, for selecting among competing partitioning strategies is proposed and tested. Improvements in both mean -lnL and estimated posterior probabilities were observed when specific models and parameter estimates were assumed for partitions of the total data set. This result is expected given that the 95% credible intervals of model parameter estimates for numerous partitions do not overlap and it reveals that different data partitions may evolve quite differently. We further demonstrate that how one partitions the data (by gene, codon position, etc.) is shown to be a greater concern than simply the overall number of partitions. Using the criterion of the 2 ln Bayes factor > 10, the phylogenetic analysis employing the largest number of partitions was decisively better than all other strategies. Strategies that partitioned the ND1 gene by codon position performed better than other partition strategies, regardless of the overall number of partitions. Scincidae, Acontinae, Lygosominae, east Asian and North American "Eumeces" + Neoseps; North African Eumeces, Scincus, and Scincopus, and a large group primarily from sub-Saharan Africa, Madagascar, and neighboring islands are monophyletic. Feylinia, a limbless group of previously uncertain relationships, is nested within a "scincine" clade from sub-Saharan Africa. We reject the hypothesis that the nearly limbless dibamids are derived from within the Scincidae, but cannot reject the hypothesis that they represent the sister taxon to skinks. Amphiglossus, Chalcides, the acontines Acontias and Typhlosaurus, and Scincinae are paraphyletic. The globally widespread "Eumeces" is polyphyletic and we make necessary taxonomic changes.     

Statistical characterization of protein ensembles

When accounting for structural fluctuations or measurement errors, a single rigid structure may not be sufficient to represent a protein. One approach to solve this problem is to represent the possible conformations as a discrete set of observed conformations, an ensemble. In this work, we follow a different richer approach, and introduce a framework for estimating probability density functions in very high dimensions, and then apply it to represent ensembles of folded proteins. This proposed approach combines techniques such as kernel density estimation, maximum likelihood, cross-validation, and bootstrapping. We present the underlying theoretical and computational framework and apply it to artificial data and protein ensembles obtained from molecular dynamics simulations. We compare the results with those obtained experimentally, illustrating the potential and advantages of this representation.     

Nhs: network-based hierarchical segmentation for cryo-electron microscopy density maps

Cryo-electron microscopy (cryo-EM) experiments yield low-resolution (3-30 ?) 3D-density maps of macromolecules. These density maps are segmented to identify structurally distinct proteins, protein domains, and subunits. Such partitioning aids the inference of protein motions and guides fitting of high-resolution atomistic structures. Cryo-EM density map segmentation has traditionally required tedious and subjective manual partitioning or semisupervised computational methods, whereas validation of resulting segmentations has remained an open problem in this field. We introduce a network-based hierarchical segmentation (Nhs) method, that provides a multi-scale partitioning, reflecting local and global clustering, while requiring no user input. This approach models each map as a graph, where map voxels constitute nodes and weighted edges connect neighboring voxels. Nhs initiates Markov diffusion (or random walk) on the weighted graph. As Markov probabilities homogenize through diffusion, an intrinsic segmentation emerges. We validate the segmentations with ground-truth maps based on atomistic models. When implemented on density maps in the 2010 Cryo-EM Modeling Challenge, Nhs efficiently and objectively partitions macromolecules into structurally and functionally relevant subregions at multiple scales.     

Primitive Fitting Based on the Efficient multiBaySAC Algorithm

Although RANSAC is proven to be robust, the original RANSAC algorithm selects hypothesis sets at random, generating numerous iterations and high computational costs because many hypothesis sets are contaminated with outliers. This paper presents a conditional sampling method, multiBaySAC (Bayes SAmple Consensus), that fuses the BaySAC algorithm with candidate model parameters statistical testing for unorganized 3D point clouds to fit multiple primitives. This paper first presents a statistical testing algorithm for a candidate model parameter histogram to detect potential primitives. As the detected initial primitives were optimized using a parallel strategy rather than a sequential one, every data point in the multiBaySAC algorithm was assigned to multiple prior inlier probabilities for initial multiple primitives. Each prior inlier probability determined the probability that a point belongs to the corresponding primitive. We then implemented in parallel a conditional sampling method: BaySAC. With each iteration of the hypothesis testing process, hypothesis sets with the highest inlier probabilities were selected and verified for the existence of multiple primitives, revealing the fitting for multiple primitives. Moreover, the updated version of the initial probability was implemented based on a memorable form of Bayes’ Theorem, which describes the relationship between prior and posterior probabilities of a data point by determining whether the hypothesis set to which a data point belongs is correct. The proposed approach was tested using real and synthetic point clouds. The results show that the proposed multiBaySAC algorithm can achieve a high computational efficiency (averaging 34% higher than the efficiency of the sequential RANSAC method) and fitting accuracy (exhibiting good performance in the intersection of two primitives), whereas the sequential RANSAC framework clearly suffers from over- and under-segmentation problems. Future work will aim at further optimizing this strategy through its application to other problems such as multiple point cloud co-registration and multiple image matching.     

Mosaicism, modules, and the evolution of birds: results from a Bayesian approach to the study of morphological evolution using discrete character data

The study of morphological evolution after the inferred origin of active flight homologous with that in Aves has historically been characterized by an emphasis on anatomically disjunct, mosaic patterns of change. Relatively few prior studies have used discrete morphological character data in a phylogenetic context to quantitatively investigate morphological evolution or mosaic evolution in particular. One such previously employed method, which used summed unambiguously optimized synapomorphies, has been the basis for proposing disassociated and sequential "modernizing" or "fine-tuning" of pectoral and then pelvic locomotor systems after the origin of flight ("pectoral early-pelvic late" hypothesis). We use one of the most inclusive phylogenetic data sets of basal birds to investigate properties of this method and to consider the application of a Bayesian phylogenetic approach. Bayes factor and statistical comparisons of branch length estimates were used to evaluate support for a mosaic pattern of character change and the specific pectoral early-pelvic late hypothesis. Partitions were defined a priori based on anatomical subregion (e.g., pelvic, pectoral) and were based on those hypothesized using the summed synapomorphy approach. We compare 80 models all implementing the M(k) model for morphological data but varying in the number of anatomical subregion partitions, the models for among-partition rate variation and among-character rate variation, as well as the branch length prior. Statistical analysis reveals that partitioning data by anatomical subregion, independently estimating branch lengths for partitioned data, and use of shared or per partition gamma-shaped among-character rate distribution significantly increases estimated model likelihoods. Simulation studies reveal that partitioned models where characters are randomly assigned perform significantly worse than both the observed model and the single-partition equal-rate model, suggesting that only partitioning by anatomical subregion increases model performance. The preference for models with partitions defined a priori by anatomical subregion is consistent with a disjunctive pattern of character change for the data set investigated and may have implications for parameterization of Bayesian analyses of morphological data more generally. Statistical tests of differences in estimated branch lengths from the pectoral and pelvic partitions do not support the specific pectoral early-pelvic late hypothesis proposed from the summed synapomorphy approach; however, results suggest limited support for some pectoral branch lengths being significantly longer only early at/after the origin of flight.     

Pseudo-periodic partitions of biological sequences

MOTIVATION: Algorithm development for finding typical patterns in sequences, especially multiple pseudo-repeats (pseudo-periodic regions), is at the core of many problems arising in biological sequence and structure analysis. In fact, one of the most significant features of biological sequences is their high quasi-repetitiveness. Variation in the quasi-repetitiveness of genomic and proteomic texts demonstrates the presence and density of different biologically important information. It is very important to develop sensitive automatic computational methods for the identification of pseudo-periodic regions of sequences through which we can infer, describe and understand biological properties, and seek precise molecular details of biological structures, dynamics, interactions and evolution. RESULTS: We develop a novel, powerful computational tool for partitioning a sequence to pseudo-periodic regions. The pseudo-periodic partition is defined as a partition, which intuitively has the minimal bias to some perfect-periodic partition of the sequence based on the evolutionary distance. We devise a quadratic time and space algorithm for detecting a pseudo-periodic partition for a given sequence, which actually corresponds to the shortest path in the main diagonal of the directed (acyclic) weighted graph constructed by the Smith-Waterman self-alignment of the sequence. We use several typical examples to demonstrate the utilization of our algorithm and software system in detecting functional or structural domains and regions of proteins. A big advantage of our software program is that there is a parameter, the granularity factor, associated with it and we can freely choose a biological sequence family as a training set to determine the best parameter. In general, we choose all repeats (including many pseudo-repeats) in the SWISS-PROT amino acid sequence database as a typical training set. We show that the granularity factor is 0.52 and the average agreement accuracy of pseudo-periodic partitions, detected by our software for all pseudo-repeats in the SWISS-PROT database, is as high as 97.6%.     

Estimation and validation of spatio-temporal parameters for sprint running using a radio-based tracking system

Spatio-temporal parameters like step length, step frequency and ground contact time are directly related to sprinting performance. There is still a lack of knowledge, however, on how these parameters interact.Recently, various algorithms for the automatic detection of step parameters during sprint running have been presented which have been based on data from motion capture systems, video cameras, opto-electronic systems or Inertial measurement units. However, all of these methods suffer from at least one of the following shortcomings: they are (a) not applicable for more than one sprinter simultaneously, (b) only capable of capturing a small volume or (c) do not provide accurate spatial parameters. To circumvent these issues, the radio-based local position measurement system RedFIR could be used to obtain spatio-temporal information during sprinting based on lightweight transmitters attached to the athletes. To assess and optimize the accuracy of these parameters 19 100 m sprints of twelve young elite athletes (age: 16.5 ± 2.3 years) were recorded by a radio-based tracking system and a opto-electronic reference instrument. Optimal filter parameters for the step detection algorithm were obtained based on RMSE differences between estimates and reference values on an unseen test set. Attaching a transmitter above the ankle showed the best results.Bland-Altman analysis yielded 95% limits of agreement of [−14.65 cm, 15.05 cm] for step length [−0.016 s, 0.016 s] for step time and [−0.020 s, 0.028 s] for ground contact time, respectively. RMS errors smaller than 2% for step length and step time show the applicability of radio-based tracking systems to provide spatio-temporal parameters. This creates new opportunities for performance analysis that can be applied for any running discipline taking place within a stadium. Since analysis for multiple athletes is available in real-time this allows immediate feedback to coaches, athletes and media.     

Robust single-particle tracking in live-cell time-lapse sequences

Single-particle tracking (SPT) is often the rate-limiting step in live-cell imaging studies of subcellular dynamics. Here we present a tracking algorithm that addresses the principal challenges of SPT, namely high particle density, particle motion heterogeneity, temporary particle disappearance, and particle merging and splitting. The algorithm first links particles between consecutive frames and then links the resulting track segments into complete trajectories. Both steps are formulated as global combinatorial optimization problems whose solution identifies the overall most likely set of particle trajectories throughout a movie. Using this approach, we show that the GTPase dynamin differentially affects the kinetics of long- and short-lived endocytic structures and that the motion of CD36 receptors along cytoskeleton-mediated linear tracks increases their aggregation probability. Both applications indicate the requirement for robust and complete tracking of dense particle fields to dissect the mechanisms of receptor organization at the level of the plasma membrane.     

A nonparametric method for accommodating and testing across-site rate variation

Substitution rates are one of the most fundamental parameters in a phylogenetic analysis and are represented in phylogenetic models as the branch lengths on a tree. Variation in substitution rates across an alignment of molecular sequences is well established and likely caused by variation in functional constraint across the genes encoded in the sequences. Rate variation across alignment sites is important to accommodate in a phylogenetic analysis; failure to account for across-site rate variation can cause biased estimates of phylogeny or other model parameters. Traditionally, rate variation across sites has been modeled by treating the rate for a site as a random variable drawn from some probability distribution (such as the gamma probability distribution) or by partitioning sites to different rate classes and estimating the rate for each class independently. We consider a different approach, related to site-specific models in which sites are partitioned to rate classes. However, instead of treating the partitioning scheme in which sites are assigned to rate classes as a fixed assumption of the analysis, we treat the rate partitioning as a random variable under a Dirichlet process prior. We find that the Dirichlet process prior model for across-site rate variation fits alignments of DNA sequence data better than commonly used models of across-site rate variation. The method appears to identify the underlying codon structure of protein-coding genes; rate partitions that were sampled by the Markov chain Monte Carlo procedure were closer to a partition in which sites are assigned to rate classes by codon position than to randomly permuted partitions but still allow for additional variability across sites.     

Single-cell behavior and population heterogeneity: solving an inverse problem to compute the intrinsic physiological state functions

The dynamics of isogenic cell populations can be described by cell population balance models that account for phenotypic heterogeneity. To utilize the predictive power of these models, however, we must know the rates of single-cell reaction and division and the bivariate partition probability density function. These three intrinsic physiological state (IPS) functions can be obtained by solving an inverse problem that requires knowledge of the phenotypic distributions for the overall cell population, the dividing cell subpopulation and the newborn cell subpopulation. We present here a robust computational procedure that can accurately estimate the IPS functions for heterogeneous cell populations. A detailed parametric analysis shows how the accuracy of the inverse solution is affected by discretization parameters, the type of non-parametric estimators used, the qualitative characteristics of phenotypic distributions and the unknown partitioning probability density function. The effect of finite sampling and measurement errors on the accuracy of the recovered IPS functions is also assessed. Finally, we apply the procedure to estimate the IPS functions of an E. coli population carrying an IPTG-inducible genetic toggle network. This study completes the development of an integrated experimental and computational framework that can become a powerful tool for quantifying single-cell behavior using measurements from heterogeneous cell populations.     

Digital IIR filters design using differential evolution algorithm with a controllable probabilistic population size

Design of a digital infinite-impulse-response (IIR) filter is the process of synthesizing and implementing a recursive filter network so that a set of prescribed excitations results a set of desired responses. However, the error surface of IIR filters is usually non-linear and multi-modal. In order to find the global minimum indeed, an improved differential evolution (DE) is proposed for digital IIR filter design in this paper. The suggested algorithm is a kind of DE variants with a controllable probabilistic (CPDE) population size. It considers the convergence speed and the computational cost simultaneously by nonperiodic partial increasing or declining individuals according to fitness diversities. In addition, we discuss as well some important aspects for IIR filter design, such as the cost function value, the influence of (noise) perturbations, the convergence rate and successful percentage, the parameter measurement, etc. As to the simulation result, it shows that the presented algorithm is viable and comparable. Compared with six existing State-of-the-Art algorithms-based digital IIR filter design methods obtained by numerical experiments, CPDE is relatively more promising and competitive.     

A molecular perspective on the evolution of microteiid lizards (Squamata, Gymnophthalmidae), and a new classification for the family

A molecular phylogeny was reconstructed for 26 recognized genera of the Gymnophthalmidae using a total of 2379 bp of mitochondrial (12S, 16S and ND4) and nuclear (18S and c-mos) DNA sequences. We performed maximum parsimony (MP) and maximum likelihood (ML) analyses, and data partitions were analysed separately and in combination under MP. ML analyses were carried out only on the combined sequences for computational simplicity. Robustness for the recovered nodes was assessed with bootstrap and partitioned Bremer support (PBS) analyses. The total molecular evidence provided a better-resolved hypothesis than did separate analysis of individual partitions, and the PBS analysis indicates congruence among independent partitions for support of some internal nodes. Based on this hypothesis, a new classification for the family is proposed. Alopoglossus , the sister group of all the other Gymnophthalmidae was allocated to a new subfamily Alopoglossinae, and Rhachisaurus (a new genus for Anotosaura brachylepis) to the new Rhachisaurinae. Two tribes are recognized within the subfamily Gymnophthalminae: Heterodactylini and Gymnophthalmini, and two others within Cercosaurinae (Ecpleopini and Cercosaurini). Some ecological and evolutionary implications of the phylogenetic hypothesis are considered, including the independent occurrence of limb reduction, body elongation, and other characters associated with fossoriality.     

Analysing grouping of nucleotides in DNA sequences using lumped processes constructed from Markov chains

The most commonly used models for analysing local dependencies in DNA sequences are (high-order) Markov chains. Incorporating knowledge relative to the possible grouping of the nucleotides enables to define dedicated sub-classes of Markov chains. The problem of formulating lumpability hypotheses for a Markov chain is therefore addressed. In the classical approach to lumpability, this problem can be formulated as the determination of an appropriate state space (smaller than the original state space) such that the lumped chain defined on this state space retains the Markov property. We propose a different perspective on lumpability where the state space is fixed and the partitioning of this state space is represented by a one-to-many probabilistic function within a two-level stochastic process. Three nested classes of lumped processes can be defined in this way as sub-classes of first-order Markov chains. These lumped processes enable parsimonious reparameterizations of Markov chains that help to reveal relevant partitions of the state space. Characterizations of the lumped processes on the original transition probability matrix are derived. Different model selection methods relying either on hypothesis testing or on penalized log-likelihood criteria are presented as well as extensions to lumped processes constructed from high-order Markov chains. The relevance of the proposed approach to lumpability is illustrated by the analysis of DNA sequences. In particular, the use of lumped processes enables to highlight differences between intronic sequences and gene untranslated region sequences.     

Additive partitioning of rarefaction curves and species-area relationships: unifying alpha-, beta- and gamma-diversity with sample size and habitat area

Additive partitioning of species diversity is widely applicable to different kinds of sampling regimes at multiple spatial and temporal scales. In additive partitioning, the diversity within and among samples ( α and β ) is expressed in the same units of species richness, thus allowing direct comparison of α and β . Despite its broad applicability, there are few demonstrated linkages between additive partitioning and other approaches to analysing diversity. Here, we establish several connections between diversity partitions and patterns of habitat occupancy, rarefaction, and species–area relationships. We show that observed partitions of species richness are equivalent to sample-based rarefaction curves, and expected partitions from randomization tests are approximately equivalent to individual-based rarefaction. Additive partitions can also be applied to species–area relationships to determine the relative contributions of factors influencing the β -diversity among habitat fragments.     

A local training and pruning approach for neural networks

The training of neural networks using the extended Kalman filter (EKF) algorithm is plagued by the drawback of high computational complexity and storage requirement that may become prohibitive even for networks of moderate size. In this paper, we present a local EKF training and pruning approach that can solve this problem. In particular, the by-products obtained along with the local EKF training can be utilized to measure the importance of the network weights. Comparing with the original global approach, the proposed local EKF training and pruning approach results in a much lower computational complexity and storage requirement. Hence, it is more practical in solving real world problems. The performance of the proposed algorithm is demonstrated on one medium- and one large-scale problems, namely, sunspot data prediction and handwritten digit recognition.