Dissertations / Theses on the topic 'Sequence similarity analysis'

This project brings the bioinformatics community a new development concept in which users can access all data and applications hosted in the main research centers as if they were installed on their local machines, providing seamless integration between disparate services. The project moves to integrate the sequence similarity searching at EBI and NCBI by using web services. It also intends to allow molecular biologists to save their searches and act as a log book for their sequence similarity searches. The project will also allow the biologists to share their sequences and results with others.

Sequence similarity searching is commonly used to help clarify the biochemical and physiological features of newly discovered genes or proteins. An efficient similarity search relies on the choice of tools and their associated subprograms and numerous parameter settings. To assist researchers in selecting optimal programs and parameter settings for efficient sequence similarity searches, the web-based expert system, Smart Sequence Similarity Search (S4) was developed.

Nous étudions l'extraction de motifs sous contraintes dans des collections de chaînes de caractères et le développement de solveurs complets et génériques pour l'extraction de tous les motifs satisfaisant une combinaison de contraintes primitives. Un solveur comme FAVST permet d'optimiser des conjonctions de contraintes dites monotones et/ou anti-monotones (e. G. , des contraintes de fréquence maximale et minimale). Nous avons voulu compléter ce type d'outil en traitant des contraintes pour la découverte de motifs tolérants aux exceptions. Nous proposons différentes définitions des occurrences approchées et l'exploitation de contraintes de fréquence approximative. Ceci nous conduit à spécifier des contraintes difficiles (e. G. , pour l'expression de la similarité) comme des conjonctions de primitives monotones et anti-monotones optimisées par notre solveur MARGUERITE. Soucieux de sa mise en ?uvre dans des processus de découverte de connaissances à partir de données, nous avons analysé le réglage des paramètres d'extraction (e. G. , quel seuil choisir pour les fréquences). Nous proposons une méthode originale pour estimer le nombre de motifs qui satisfont une contrainte au moyen d'un échantillonnage de l'espace des motifs. Nous avons également étudié l'identification des paramètres les plus stringents pour fournir des motifs qui ne sont probablement pas de faux positifs. Ces contributions ont été appliquées à l'analyse des séquences promotrices des gènes. En étroite collaboration avec une équipe de biologistes du CGMC, nous avons pu identifier des sites de fixation putatifs de facteurs transcription impliqués dans le processus de différenciation cellulaire
An inductive database is a database that contains not only data but also patterns. Inductive databases are designed to support the KDD process. Recent advances in inductive databases research have given rise to a generic solvers capable of solving inductive queries that are arbitrary Boolean combinations of anti-monotonic and monotonic constraints. They are designed to mine different types of pattern (i. E. , patterns from different pattern languages). An instance of such a generic solver exists that is capable of mining string patterns from string data sets. In our main application, promoter sequence analysis, there is a requirement to handle fault-tolerance, as the data intrinsically contains errors, and the phenomenon we are trying to capture is fundamentally degenerate. Our research contribution to fault-tolerant pattern extraction in string data sets is the use of a generic solver, based on a non-trivial formalisation of fault-tolerant pattern extraction as a constraint-based mining task. We identified the stages in the process of the extraction of such patterns where state-of-art strategies can be applied to prune the search space. We then developed a fault-tolerant pattern match function InsDels that generic constraint solving strategies can soundly tackle. We also focused on making local patterns actionable. The bottleneck of most local pattern extraction methods is the burden of spurious patterns. As the analysis of patterns by the application domain experts is time consuming, we cannot afford to present patterns without any objective clue about their relevancy. Therefore we have developed two methods of computing the expected number of patterns extracted in random data sets. If the number of extracted patterns is strongly different from the expected number from random data sets, one can then state that the results exhibits local associations that are a priori relevant because they are unexpected. Among others applications, we have applied our approach to support the discovery of new motifs in gene promoter sequences with promising results

The advent of high-throughput sequencing and structure determination techniques has had a tremendous impact on our quest in cracking the language of life. The genomic and protein data is now being accumulated at a phenomenal rate, with the motivation of deriving insights into the function, mechanism, and evolution of the biomolecules, through analysis of their similarities, differences, and interactions. The rapid increase in the size of the biomolecular databases, however, calls for development of new computational methods for sensitive and efficient management and analysis of this information. In this thesis, we propose and implement several approaches for accurate and highly efficient comparison and retrieval of protein sequences and structures. The observation that corresponding residues in related proteins share similar inter-residue contacts is exploited in derivation of a new set of biologically sensitive metric amino acid substitution matrices, yielding accurate alignment and comparison of proteins. The metricity of these matrices has allowed efficient indexing and retrieval of both protein sequences and structures. A landmark-guided embedding of protein sequences is developed to represent subsequences in a vector space for approximate, but extremely fast spatial indexing and similarity search. Whereas protein structure comparison and search tasks were hitherto handled separately, we propose an integrated approach that serves both of these tasks and performs comparable to or better than other available methods. Our approach hinges on identification of similar residue contacts using distance-based indexing and provides the best of the both worlds: the accuracy of detailed structure alignment algorithms, at a speed comparable to that of the structure retrieval algorithms. We expect that the methods and tools developed in this study will find use in a wide range of application areas including annotation of new proteins, discovery of functional motifs, discerning evolutionary relationships among genes and species, and drug design and targeting.

Thesis (Ph. D.)--University of California, San Diego and San Diego State University, 2006.
Title from first page of PDF file (viewed December 12, 2006). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references.

Complex networks have been studied extensively due to their relevance to many real-world systems such as the world-wide web, the internet, biological and social systems. During the past two decades, studies of such networks in different fields have produced many significant results concerning their structures, topological properties, and dynamics. Three well-known properties of complex networks are scale-free degree distribution, small-world effect and self-similarity. The search for additional meaningful properties and the relationships among these properties is an active area of current research. This thesis investigates a newer aspect of complex networks, namely their multifractality, which is an extension of the concept of selfsimilarity. The first part of the thesis aims to confirm that the study of properties of complex networks can be expanded to a wider field including more complex weighted networks. Those real networks that have been shown to possess the self-similarity property in the existing literature are all unweighted networks. We use the proteinprotein interaction (PPI) networks as a key example to show that their weighted networks inherit the self-similarity from the original unweighted networks. Firstly, we confirm that the random sequential box-covering algorithm is an effective tool to compute the fractal dimension of complex networks. This is demonstrated on the Homo sapiens and E. coli PPI networks as well as their skeletons. Our results verify that the fractal dimension of the skeleton is smaller than that of the original network due to the shortest distance between nodes is larger in the skeleton, hence for a fixed box-size more boxes will be needed to cover the skeleton. Then we adopt the iterative scoring method to generate weighted PPI networks of five species, namely Homo sapiens, E. coli, yeast, C. elegans and Arabidopsis Thaliana. By using the random sequential box-covering algorithm, we calculate the fractal dimensions for both the original unweighted PPI networks and the generated weighted networks. The results show that self-similarity is still present in generated weighted PPI networks. This implication will be useful for our treatment of the networks in the third part of the thesis. The second part of the thesis aims to explore the multifractal behavior of different complex networks. Fractals such as the Cantor set, the Koch curve and the Sierspinski gasket are homogeneous since these fractals consist of a geometrical figure which repeats on an ever-reduced scale. Fractal analysis is a useful method for their study. However, real-world fractals are not homogeneous; there is rarely an identical motif repeated on all scales. Their singularity may vary on different subsets; implying that these objects are multifractal. Multifractal analysis is a useful way to systematically characterize the spatial heterogeneity of both theoretical and experimental fractal patterns. However, the tools for multifractal analysis of objects in Euclidean space are not suitable for complex networks. In this thesis, we propose a new box covering algorithm for multifractal analysis of complex networks. This algorithm is demonstrated in the computation of the generalized fractal dimensions of some theoretical networks, namely scale-free networks, small-world networks, random networks, and a kind of real networks, namely PPI networks of different species. Our main finding is the existence of multifractality in scale-free networks and PPI networks, while the multifractal behaviour is not confirmed for small-world networks and random networks. As another application, we generate gene interactions networks for patients and healthy people using the correlation coefficients between microarrays of different genes. Our results confirm the existence of multifractality in gene interactions networks. This multifractal analysis then provides a potentially useful tool for gene clustering and identification. The third part of the thesis aims to investigate the topological properties of networks constructed from time series. Characterizing complicated dynamics from time series is a fundamental problem of continuing interest in a wide variety of fields. Recent works indicate that complex network theory can be a powerful tool to analyse time series. Many existing methods for transforming time series into complex networks share a common feature: they define the connectivity of a complex network by the mutual proximity of different parts (e.g., individual states, state vectors, or cycles) of a single trajectory. In this thesis, we propose a new method to construct networks of time series: we define nodes by vectors of a certain length in the time series, and weight of edges between any two nodes by the Euclidean distance between the corresponding two vectors. We apply this method to build networks for fractional Brownian motions, whose long-range dependence is characterised by their Hurst exponent. We verify the validity of this method by showing that time series with stronger correlation, hence larger Hurst exponent, tend to have smaller fractal dimension, hence smoother sample paths. We then construct networks via the technique of horizontal visibility graph (HVG), which has been widely used recently. We confirm a known linear relationship between the Hurst exponent of fractional Brownian motion and the fractal dimension of the corresponding HVG network. In the first application, we apply our newly developed box-covering algorithm to calculate the generalized fractal dimensions of the HVG networks of fractional Brownian motions as well as those for binomial cascades and five bacterial genomes. The results confirm the monoscaling of fractional Brownian motion and the multifractality of the rest. As an additional application, we discuss the resilience of networks constructed from time series via two different approaches: visibility graph and horizontal visibility graph. Our finding is that the degree distribution of VG networks of fractional Brownian motions is scale-free (i.e., having a power law) meaning that one needs to destroy a large percentage of nodes before the network collapses into isolated parts; while for HVG networks of fractional Brownian motions, the degree distribution has exponential tails, implying that HVG networks would not survive the same kind of attack.

La réduction des coûts et l'amélioration du débit de la technologie de séquençage ont entraîné de nouvelles avancées dans des applications telles que la médecine de précision et le stockage basé sur l'ADN. Cependant, le résultat séquencé contient des erreurs. Pour mesurer la similitude entre le résultat séquencé et la référence, la distance d'édition est préférée en pratique à la distance de Hamming en raison des indels. Le calcul de la distance d'édition est complexe quadratique. Par conséquent, l'analyse de similarité de séquence nécessite beaucoup de calculs. Dans cette thèse, nous introduisons deux algorithmes d'analyse de similarité de séquence précis et évolutifs, i) Accel-Align, un mappeur et un aligneur de séquence rapide basé sur la méthodologie seed–embed–extend, et ii) Motif-Search, une structure-efficace algorithme conscient pour récupérer les informations codées par les motifs composites à partir de l'archive ADN. Ensuite, nous utilisons Accel-Align comme un outil efficace pour étudier la conception d'accès aléatoire dans le stockage basé sur l'ADN
Cost reduction and throughput improvement in sequencing technology have resulted in new advances in applications such as precision medicine and DNA-based storage. However, the sequenced result contains errors. To measure the similarity between the sequenced result and reference, edit distance is preferred in practice over Hamming distance due to the indels. The primitive edit distance calculation is quadratic complex. Therefore, sequence similarity analysis is computationally intensive. In this thesis, we introduce two accurate and scalable sequence similarity analysis algorithms, i) Accel-Align, a fast sequence mapper and aligner based on the seed–embed–extend methodology, and ii) Motif-Search, an efficient structure-aware algorithm to recover the information encoded by the composite motifs from the DNA archive. Then, we use Accel-Align as an efficient tool to study the random access design in DNA-based storage

Psychology
Ph.D.
Why are some memories easy to retrieve, while others are more difficult to access? Here, we tested whether we could bias memory replay, a process whereby newly learned information is reinforced by reinstating the neuronal patterns of activation that were present during learning, towards particular memory traces. The goal of this biasing is to strengthen some memory traces, making them more easily retrieved. To test this, participants were scanned during interleaved periods of encoding and rest. Throughout the encoding runs, participants learned triplets of images that were paired with semantically related sound cues. During two of the three rest periods, novel, irrelevant sounds were played. During one critical rest period, however, the sound cues learned in the preceding encoding period were played in an effort to preferentially increase reactivation of the associated visual images, a manipulation known as targeted memory reactivation. Representational similarity analyses were used to compare multi-voxel patterns of hippocampal activation across encoding and rest periods. Our index of reactivation was selectively enhanced for memory traces that were targeted for preferential reactivation during offline rest, both compared to information that was not targeted for preferential reactivation and compared to a baseline rest period. Importantly, this neural effect of targeted reactivation was related to the difference in delayed order memory for information that was cued versus uncued, suggesting that preferential replay may be a mechanism by which specific memory traces can be selectively strengthened for enhanced subsequent memory retrieval. We also found partial evidence of discrimination of unique temporal sequences within the hippocampus. Over time, multi-voxel patterns associated with a given triplet sequence became more dissimilar to the patterns associated with the other sequences. Furthermore, this neural marker of sequence preservation was correlated with the difference in delayed order memory for cued versus uncued triplets, signifying that the ability to reactivate particular temporal sequences within the hippocampus may be related to enhanced temporal order memory for the cued information. Taken together, these findings support the claim that awake replay can be biased towards preferential reactivation of particular memory traces and also suggest that this preferential reactivation, as well as representations of reactivated temporal sequences, can be detected within patterns of hippocampal activation.
Temple University--Theses

Time series data mining is one branch of data mining. Time series analysis and prediction have always played an important role in human activities and natural sciences. A Pseudo-Periodical time series has a complex structure, with fluctuations and frequencies of the times series changing over time. Currently, Pseudo-Periodicity of time series brings new properties and challenges to time series analysis and prediction. This thesis proposes two original computational approaches for time series analysis and prediction: Moving Average of nth-order Difference (MANoD) and Series Features Extraction (SFE). Based on data-driven methods, the two original approaches open new insights in time series analysis and prediction contributing with new feature detection techniques. The proposed algorithms can reveal hidden patterns based on the characteristics of time series, and they can be applied for predicting forthcoming events. This thesis also presents the evaluation results of proposed algorithms on various pseudo-periodical time series, and compares the predicting results with classical time series prediction methods. The results of the original approaches applied to real world and synthetic time series are very good and show that the contributions open promising research directions.

Submitted by Fabricia Fialho Reginato (fabriciar) on 2015-08-26T23:54:22Z No. of bitstreams: 1 TiagoWiedemann.pdf: 5635533 bytes, checksum: c0d3805abbcaf56aa36da4d8422457b6 (MD5)
Made available in DSpace on 2015-08-26T23:54:22Z (GMT). No. of bitstreams: 1 TiagoWiedemann.pdf: 5635533 bytes, checksum: c0d3805abbcaf56aa36da4d8422457b6 (MD5) Previous issue date: 2014
CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
CNPQ – Conselho Nacional de Desenvolvimento Científico e Tecnológico
A Computação Ubíqua, que estuda formas de integrar a tecnologia ao cotidiano das pessoas, é uma área que vem crescendo nos últimos anos, especialmente devido ao desenvolvimento de tecnologias como a computação móvel. Um dos aspectos fundamentais para o desenvolvimento deste tipo de aplicação é a questão da Sensibilidade ao Contexto, que permite a uma aplicação adaptar o seu funcionamento conforme a situação na qual o usuário se encontra no momento. Com esta finalidade, diversos autores apresentaram definições formais sobre o que é um contexto e como representá-lo. A partir desta formalização começaram a ser desenvolvidas técnicas para análise de dados contextuais que propunham a realização de predições e inferências, entre outras análises. Esta dissertação especifica um framework denominado SIMCOP (SIMilar Context Path) para a realização da análise de similaridade entre sequências de contextos visitados por uma entidade. Este tipo de análise permite a identificação de contextos semelhantes com a intenção de prover funcionalidades como a recomendação de entidades e/ou contextos, a classificação de entidades e a predição de contextos. Um protótipo do framework foi implementado, e a partir dele foram desenvolvidas duas aplicações de recomendação, uma delas por um desenvolvedor independente, através do qual foi possível avaliar a eficácia do framework. Com o desenvolvimento desta pesquisa comprovou-se, conforme demonstrado nas avaliações realizadas, que a análise de similaridade de contextos pode ser útil em outras áreas além da computação ubíqua, como a mineração de dados e os sistemas de filtragem colaborativa, entre outras áreas, onde qualquer conjunto de dados que puder ser descrito na forma de um contexto, poderá ser analisado através das técnicas de análise de similaridade implementadas pelo framework.
The Ubiquitous Computing, that studies the ways to integrate technology into the people’s everyday life, is an area that has been growing in recent years, especially due to the development of technologies such as mobile computing. A key for the development of this type of application is the issue of context awareness, which enables an application to self adapt to the situation in which the user is currently on. To make this possible, it was necessary to formally define what is a context and how to represent it . From this formalization, techniques for analyzing contextual data have been proposed for development of functions as predictions or inferences. This paper specifies a framework called SIMCOP (SIMilar Context Path ) for performing the analysis of similarity between sequences of contexts visited by an entity. This type of analysis enables the identification of similar contexts with the intention to provide features such as the recommendation of entities and contexts, the entities classification and the prediction of contexts. The development of this research shows that the contexts similarity analysis can be useful in other areas further the ubiquitous computing, such as data mining and collaborative filtering systems. Any data type that can be described as a context, can be analyzed through the techniques of similarity analysis implemented by the framework, as demonstrated in the assessments.

In this thesis I hope to provide a clear and concise introduction to Feigenbaum scaling accessible to undergraduate students. This is accompanied by a description of how to obtain numerical results by various means. A more intricate approach drawing from renormalization theory as well as a short consideration of some of the topological properties will also be presented. I was furthermore trying to put great emphasis on diagrams throughout the text to make the contents more comprehensible and intuitive.

Wong, Siu Fung.
Thesis submitted in: December 2003.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2004.
Includes bibliographical references (leaves 77-84).
Abstracts in English and Chinese.
Abstract --- p.ii
Acknowledgement --- p.vi
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Preliminary --- p.6
Chapter 2.1 --- Dynamic Time Warping (DTW) --- p.6
Chapter 2.2 --- Spatial Indexing --- p.10
Chapter 2.3 --- Relevance Feedback --- p.11
Chapter 3 --- Literature Review --- p.13
Chapter 3.1 --- Searching Sequences under Euclidean Metric --- p.13
Chapter 3.2 --- Searching Sequences under Dynamic Time Warping Metric --- p.17
Chapter 4 --- Subsequence Matching under Time Warping --- p.21
Chapter 4.1 --- Subsequence Matching --- p.22
Chapter 4.1.1 --- Sequential Search --- p.22
Chapter 4.1.2 --- Indexing Scheme --- p.23
Chapter 4.2 --- Lower Bound Technique --- p.25
Chapter 4.2.1 --- Properties of Lower Bound Technique --- p.26
Chapter 4.2.2 --- Existing Lower Bound Functions --- p.27
Chapter 4.3 --- Point-Based indexing --- p.28
Chapter 4.3.1 --- Lower Bound for subsequences matching --- p.28
Chapter 4.3.2 --- Algorithm --- p.35
Chapter 4.4 --- Rectangle-Based indexing --- p.37
Chapter 4.4.1 --- Lower Bound for subsequences matching --- p.37
Chapter 4.4.2 --- Algorithm --- p.41
Chapter 4.5 --- Experimental Results --- p.43
Chapter 4.5.1 --- Candidate ratio vs Width of warping window --- p.44
Chapter 4.5.2 --- CPU time vs Number of subsequences --- p.45
Chapter 4.5.3 --- CPU time vs Width of warping window --- p.46
Chapter 4.5.4 --- CPU time vs Threshold --- p.46
Chapter 4.6 --- Summary --- p.47
Chapter 5 --- Relevance Feedback under Time Warping --- p.49
Chapter 5.1 --- Integrating Relevance Feedback with DTW --- p.49
Chapter 5.2 --- Query Reformulation --- p.53
Chapter 5.2.1 --- Constraint Updating --- p.53
Chapter 5.2.2 --- Weight Updating --- p.55
Chapter 5.2.3 --- Overall Strategy --- p.58
Chapter 5.3 --- Experiments and Evaluation --- p.59
Chapter 5.3.1 --- Effectiveness of the strategy --- p.61
Chapter 5.3.2 --- Efficiency of the strategy --- p.63
Chapter 5.3.3 --- Usability --- p.64
Chapter 5.4 --- Summary --- p.71
Chapter 6 --- Conclusion --- p.72
Chapter A --- Deduction of Data Bounding Hyper-rectangle --- p.74
Chapter B --- Proof of Theorem2 --- p.76
Bibliography --- p.77
Publications --- p.84

Graphs that evolve over time are called temporal graphs. They can be used to describe and represent real-world networks, including transportation networks, social networks, and communication networks, with higher fidelity and accuracy. However, research is still limited on how to manage large scale temporal graphs and execute queries over these graphs efficiently and effectively. This thesis investigates the problems of temporal graph data management related to node and edge sequence queries. In temporal graphs, nodes and edges can evolve over time. Therefore, sequence queries on nodes and edges can be key components in managing temporal graphs. In this thesis, the node sequence query decomposes into two parts: graph node similarity and subsequence matching. For node similarity, this thesis proposes a modified tree edit distance that is metric and polynomially computable and has a natural, intuitive interpretation. Note that the proposed node similarity works even for inter-graph nodes and therefore can be used for graph de-anonymization, network transfer learning, and cross-network mining, among other tasks. The subsequence matching query proposed in this thesis is a framework that can be adopted to index generic sequence and time-series data, including trajectory data and even DNA sequences for subsequence retrieval. For edge sequence queries, this thesis proposes an efficient storage and optimized indexing technique that allows for efficient retrieval of temporal subgraphs that satisfy certain temporal predicates. For this problem, this thesis develops a lightweight data management engine prototype that can support time-sensitive temporal graph analytics efficiently even on a single PC.

1D protein sequences, 2D contact maps and 3D structures are three different representational levels of detail for proteins. Predicting protein 3D structures from their 1D sequences remains one of the complex challenges of bioinformatics. The "Divide and Conquer" principle is applied in our research to handle this challenge, by dividing it into two separate yet dependent subproblems, using a Case-Based Reasoning (CBR) approach. Firstly, 2D contact maps are predicted from their 1D protein sequences; secondly, 3D protein structures are then predicted from their predicted 2D contact maps. We focus on the problem of identifying common substructural patterns of protein contact maps, which could potentially be used as building blocks for a bottom-up approach for protein structure prediction. We further demonstrate how to improve identifying these patterns by combining both protein sequence and structural information. We assess the consistency and the efficiency of identifying common substructural patterns by conducting statistical analyses on several subsets of the experimental results with different sequence and structural information.
Thesis (Master, Computing) -- Queen's University, 2009-04-23 22:01:04.528