Rozprawy doktorskie na temat „Sequence similarity analysis”

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.<br>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<br>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<br>Ph.D.<br>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.<br>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)<br>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<br>CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior<br>CNPQ – Conselho Nacional de Desenvolvimento Científico e Tecnológico<br>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.<br>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.<br>Thesis submitted in: December 2003.<br>Thesis (M.Phil.)--Chinese University of Hong Kong, 2004.<br>Includes bibliographical references (leaves 77-84).<br>Abstracts in English and Chinese.<br>Abstract --- p.ii<br>Acknowledgement --- p.vi<br>Chapter 1 --- Introduction --- p.1<br>Chapter 2 --- Preliminary --- p.6<br>Chapter 2.1 --- Dynamic Time Warping (DTW) --- p.6<br>Chapter 2.2 --- Spatial Indexing --- p.10<br>Chapter 2.3 --- Relevance Feedback --- p.11<br>Chapter 3 --- Literature Review --- p.13<br>Chapter 3.1 --- Searching Sequences under Euclidean Metric --- p.13<br>Chapter 3.2 --- Searching Sequences under Dynamic Time Warping Metric --- p.17<br>Chapter 4 --- Subsequence Matching under Time Warping --- p.21<br>Chapter 4.1 --- Subsequence Matching --- p.22<br>Chapter 4.1.1 --- Sequential Search --- p.22<br>Chapter 4.1.2 --- Indexing Scheme --- p.23<br>Chapter 4.2 --- Lower Bound Technique --- p.25<br>Chapter 4.2.1 --- Properties of Lower Bound Technique --- p.26<br>Chapter 4.2.2 --- Existing Lower Bound Functions --- p.27<br>Chapter 4.3 --- Point-Based indexing --- p.28<br>Chapter 4.3.1 --- Lower Bound for subsequences matching --- p.28<br>Chapter 4.3.2 --- Algorithm --- p.35<br>Chapter 4.4 --- Rectangle-Based indexing --- p.37<br>Chapter 4.4.1 --- Lower Bound for subsequences matching --- p.37<br>Chapter 4.4.2 --- Algorithm --- p.41<br>Chapter 4.5 --- Experimental Results --- p.43<br>Chapter 4.5.1 --- Candidate ratio vs Width of warping window --- p.44<br>Chapter 4.5.2 --- CPU time vs Number of subsequences --- p.45<br>Chapter 4.5.3 --- CPU time vs Width of warping window --- p.46<br>Chapter 4.5.4 --- CPU time vs Threshold --- p.46<br>Chapter 4.6 --- Summary --- p.47<br>Chapter 5 --- Relevance Feedback under Time Warping --- p.49<br>Chapter 5.1 --- Integrating Relevance Feedback with DTW --- p.49<br>Chapter 5.2 --- Query Reformulation --- p.53<br>Chapter 5.2.1 --- Constraint Updating --- p.53<br>Chapter 5.2.2 --- Weight Updating --- p.55<br>Chapter 5.2.3 --- Overall Strategy --- p.58<br>Chapter 5.3 --- Experiments and Evaluation --- p.59<br>Chapter 5.3.1 --- Effectiveness of the strategy --- p.61<br>Chapter 5.3.2 --- Efficiency of the strategy --- p.63<br>Chapter 5.3.3 --- Usability --- p.64<br>Chapter 5.4 --- Summary --- p.71<br>Chapter 6 --- Conclusion --- p.72<br>Chapter A --- Deduction of Data Bounding Hyper-rectangle --- p.74<br>Chapter B --- Proof of Theorem2 --- p.76<br>Bibliography --- p.77<br>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.<br>Thesis (Master, Computing) -- Queen's University, 2009-04-23 22:01:04.528