No description available.

No description available.

No description available.

Genetic research projects currently can require enormous computing power to processes the vast quantities of data available. Further, DNA sequencing projects are generating data at an exponential rate greater than that of the development microprocessor technology; thus, new, faster methods and techniques of processing this data are needed. One common type of processing involves searching a sequence database for the most similar sequences. Here we present a distributed database search system that utilizes adaptive computing technologies. The search is performed using the Smith-Waterman algorithm, a common sequence comparison algorithm. To reduce the total search time, an initial search is performed using a version of the algorithm, implemented in adaptive computing hardware, which is designed to efficiently perform the initial search. A final search is performed using a complete version of the algorithm. This two-stage search, employing adaptive and distributed hardware, achieves a performance increase of several orders of magnitude over similar processor based systems. / Master of Science

Measuring the amount of information and of shared information in biological strings, as well as relating information to structure, function and evolution, are fundamental computational problems in the post-genomic era. Classical analyses of the information content of biosequences are grounded in Shannon's statistical telecommunication theory, while the recent focus is on suitable specializations of the notions introduced by Kolmogorov, Chaitin and Solomonoff, based on data compression and compositional redundancy. Symmetrically, classical estimates of mutual information based on string editing are currently being supplanted by compositional methods hinged on the distribution of controlled substructures. Current compositional analyses and comparisons of biological strings are almost exclusively limited to short sequences of contiguous solid characters. Comparatively little is known about longer and sparser components, both from the point of view of their effectiveness in measuring information and in separating biological strings from random strings, and from the point of view of their ability to classify and to reconstruct phylogenies. Yet, sparse structures are suspected to grasp long-range correlations and, at short range, they are known to encode signatures and motifs that characterize molecular families. In this thesis, we introduce and study compositional measures based on the repertoire of distinct subsequences of any length, but constrained to occur with a predefined maximum gap between consecutive symbols. Such measures highlight previously unknown laws that relate subsequence abundance to string length and to the allowed gap, across a range of structurally and functionally diverse polypeptides. Measures on subsequences are capable of separating only few amino acid strings from their random permutations, but they reveal that random permutations themselves amass along previously undetected, linear loci. This is perhaps the first time in which the vocabulary of all distinct subsequences of a set of structurally and functionally diverse polypeptides is systematically counted and analyzed. Another objective of this thesis is measuring the quality of phylogenies based on the composition of sparse structures. Specifically, we use a set of repetitive gapped patterns, called motifs, whose length and sparsity have never been considered before. We find that extremely sparse motifs in mitochondrial proteomes support phylogenies of comparable quality to state-of-the-art string-based algorithms. Moving from maximal motifs -- motifs that cannot be made more specific without losing support -- to a set of generators with decreasing size and redundancy, generally degrades classification, suggesting that redundancy itself is a key factor for the efficient reconstruction of phylogenies. This is perhaps the first time in which the composition of all motifs of a proteome is systematically used in phylogeny reconstruction on a large scale. Extracting all maximal motifs, or even their compact generators, is infeasible for entire genomes. In the last part of this thesis, we study the robustness of measures of similarity built around the dictionary of LZW -- the variant of the LZ78 compression algorithm proposed by Welch -- and of some of its recently introduced gapped variants. These algorithms use a very small vocabulary, they perform linearly in the input strings, and they can be made even faster than LZ77 in practice. We find that dissimilarity measures based on maximal strings in the dictionary of LZW support phylogenies that are comparable to state-of-the-art methods on test proteomes. Introducing a controlled proportion of gaps does not degrade classification, and allows to discard up to 20% of each input proteome during comparison.

The present dissertation develops an invariant framework for 3D gesture comparison studies. 3D gesture comparison without Lagrangian models is challenging not only because of the lack of prediction provided by physics, but also because of a dual geometry representation, spatial dimensionality and non-linearity associated to 3D-kinematics. In 3D spaces, it is difficult to compare curves without an alignment operator since it is likely that discrete curves are not synchronized and do not share a common point in space. One has to assume that each and every single trajectory in the space is unique. The common answer is to assert the similitude between two or more trajectories as estimating an average distance error from the aligned curves, provided that the alignment operator is found. In order to avoid the alignment problem, the method uses differential geometry for position and orientation curves. Differential geometry not only reduces the spatial dimensionality but also achieves view invariance. However, the nonlinear signatures may be unbounded or singular. Yet, it is shown that pattern recognition between intrinsic signatures using correlations is robust for position and orientation alike. A new mapping for orientation sequences is introduced in order to treat quaternion and Euclidean intrinsic signatures alike. The new mapping projects a 4D-hyper-sphere for orientations onto a 3D-Euclidean volume. The projection uses the quaternion invariant distance to map rotation sequences into 3D-Euclidean curves. However, quaternion spaces are sectional discrete spaces. The significance is that continuous rotation functions can be only approximated for small angles. Rotation sequences with large angle variations can only be interpolated in discrete sections. The current dissertation introduces two multi-scale approaches that improve numerical stability and bound the signal energy content of the intrinsic signatures. The first is a multilevel least squares curve fitting method similar to Haar wavelet. The second is a geodesic distance anisotropic kernel filter. The methodology testing is carried out on 3D-gestures for obstetrics training. The study quantitatively assess the process of skill acquisition and transfer of manipulating obstetric forceps gestures. The results show that the multi-scale correlations with intrinsic signatures track and evaluate gesture differences between experts and trainees.

No description available.