Abstract

One of the main goals of modern biotechnology and biophysics is to understand the structure and interactions of biomolecules such as nucleic acids and proteins. The complexity in understanding the living systems and the processes occurring in them primarily revolves around these biomolecules. Understanding the molecular level details of such processes is difficult and is not always possible using experimental methods. Computational methods prove to be efficient alternative tools in studying the atomistic details of molecular processes. Molecular dynamics (MD) simulation is one such method that is extremely used to study structure-function relationships of biomolecules. The present thesis has two parts: heterogeneous nucleic acids and homogeneous nucleic acids. The heterogeneous nucleic acids include DNA-RNA hybrids, locked nucleic acids and 2’-O-methyl modified duplexes that have a wide range of applications in nucleic acid-based therapies. Extensive analyses of MD trajectories suggest that the structural and energetic properties of DNA-RNA hybrids depend on the extent of mixing of base composition in their DNA strand. However, such variations were not seen in their RNA strand. The MD simulation results also showed that the decreasing deoxypyrimidine composition in DNA strand leads to transformation of the DNA-RNA hybrid conformation from A-type to A/B-type. The possible factors responsible for the inactivity of ribonuclease H (RNase H) enzyme towards hybrids with high deoxypyrimidine composition have also been proposed. Thermodynamic stabilities of the duplexes were explained by using binding free energies. Next, investigations have been carried out to understand the interactions between rnase H enzyme with the DNA-RNA hybrid and the energy cost accompanying the complex formation. The binding of enzyme to the nucleic acid induces conformational transitions towards N-type or S-type in deoxyribose sugars that are important for efficient binding. Since this enzyme exhibit close structural and functional similarity with RNase H of the HIV-I reverse transcriptase and several other nucleic acid processing enzymes, the present study is helpful in understanding the molecular level details of their dynamics and stability. A comprehensive study has been performed on DNA-RNA hybrid duplexes by systematically modifying the deoxyribose sugars to isomeric locked nucleic acid (α/β-LNA) modifications; which leads to increase in duplex stability and change in conformation to A-type. The differential effects of these two modifications were studied extensively. The results indicate that the α-LNA modification induces conformational changes in the duplex backbone in order to adjust in the duplex. However, such changes are not necessary for β-LNA modification. The structure and thermodynamic stabilities of the full LNA duplexes have also been explored. Free energy calculations suggest that hydrophobicity of 2'-O-Methyl groups is primarily responsible for the reversal thermodynamic stabilities of DNA-RNA hybrids. RNA molecules have been shown to fold to form complex three-dimensional structures that are important for catalytic cellular processes. Investigation of RNA folding is crucial for understanding its diverse functions. RNA folding dynamics has been studied by taking a 12 nucleotide GNRA RNA hairpin in water, urea and MgCl 2 solutions using replica exchange molecular dynamics simulations. Urea decreases the melting temperature of the RNA hairpin while Mg 2+ increases melting temperature that agree well with the experimental data. Urea reduces the hydrogen bonding interactions of base pairs and stacking interactions among nucleobases that results in faster unfolding of RNA hairpin. Urea prevents refolding of hairpin by forming strong hydrogen bond and stacking interactions with the nucleobases when the nucleobases separate from hairpin during unfolding process. The components of calculated interaction energies suggest that dispersion interactions play key role in RNA denaturation and unfolding processes.

Abstract

Advances in cloud computing have redefined the landscape of modern information technology as seen by the popularity of cloud service providers such as Amazon, Microsoft Azure and Google App Engine. Data storage outsourcing is a prime application in cloud computing, which allows organizations to provide reliable data services to users without concerning with the data management overheads. But, there are several practical apprehensions regarding the privacy of the outsourced data and these concerns are a major hindrance towards the uninhibited adoption of cloud storage services. Generally, the cloud service provider does not attempt to violate data privacy, there are internal factors like malicious employees who will abuse the client data at the first available opportunity. Thus, the data needs to be encrypted prior to outsourcing. However, the encryption is a major hindrance to perform regular data access operations, such as searching for documents containing specific keywords or patterns. Therefore, there is a crucial need for techniques to support a rich set of querying functionality on the encrypted data without violating the privacy of the users. While there have been many works on efficiently solving the problem of privacy preserving single keyword and multi-keyword search on outsourced data in cloud computing, both in public key and symmetric key domains, the problem of privacy preserving string pattern search has only been solved in public key domain and that too is not efficient enough for adopting to practical scenarios like cloud. We note that the solution to this problem is unexplored in symmetric key domain. In this work, we present the first ever symmetric key based approach to support privacy preserving string pattern matching on outsourced data in cloud computing. String pattern matching functionality can find occurrence of a string pattern anywhere within a keyword. We describe an efficient and accurate indexing structure, the PASStree, which can execute a string pattern query in logarithmic time complexity over a set of data items. The PASStree provides strong privacy guarantees against attacks from a semi-honest adversary. We have comprehensively evaluated our scheme over large real-life data, such as Wikipedia and Enron documents, containing up to 100000 keywords, and show that our algorithms achieve pattern search in less than a few milliseconds with 100% accuracy. We have performed prefix and sub-string pattern search on Wikipedia dataset, and performed multi-keyword phrase search of sender/receiver queries on Enron dataset. Furthermore, we also describe a relevance ranking algorithm to return the most relevant documents to the user based on the query pattern. Our ranking algorithm achieves 90%+ above precision in ranking the returned documents.

Abstract

An overlay network is a logical network built on top of some underlying network (the underlay) with an objective to provide some service to the underlying network. The internet, for instance, was initially an overlay network built on top of the Public Switched Telephone Network and has today become the underlying substrate for overlay networks of numerous types - peer-to-peer file sharing (BitTorrent), multimedia (Skype), security (VPNs), experimental test beds (PlanetLab), etc. Pioneered by Napster in 1999 and strongly purported by further advances like Gnutella, Kaaza, Freenet, shortly thereafter, peer-to-peer content sharing became quite popular across a wide range of internet audience during the early 2000s and has been growing ever since. As a result, peer-to-peer systems (not just file sharing), in general, are today some of the most popular overlay applications across the internet. Peer-to-peer overlay networks can be classified into two broad categories - structured and unstructured. In the unstructured category, any peer may host any content which means that in order to find a specific content, only a blind search can be carried out in the overlay. In the structured category, on the other hand, a tight relation is defined between the content and its host, such that any peer in the overlay, given the content to be searched, can compute the identity of the peer hosting the content. Therefore, while in an unstructured P2P overlay, data storage is random and data search is blind or at best heuristic, in a structured P2P overlay, data storage is controlled and, as a result, data search is structured. The way we see it, the structured category can be characterized by a couple of components - the mapping component that maps the data items to one or more overlay nodes and the overlay nodes to the underlay peers, i.e., one that takes care of distribution/re-distribution of the data to be hosted on the overlay among the overlay nodes and the routing component that creates the overlay routing topology in a way that every peer in the overlay can deterministically figure out which outgoing link must be chosen to reach a given destination peer in the overlay. So, for any data search, while the mapping component tells us where - on which overlay node - the data resides, the routing component tells us how to get there. In this work, we formalize the routing component of structured P2P overlay networks and mathematically analyze the overlay properties determined/affected by it. Unless explicitly qualified, throughout thiswork, by structured overlay networks (short hand SONs), or structured overlays or simply overlays, we shall mean structured P2P overlay networks.

Abstract

In the recent past, the Web has not only become the predominant source of information, but also a crucial player in the evolution of events. People reporting information about real time events has made it a significant indicator to detect and estimate the pulse of various communities. Currently the most amount of real-time information about events is generated by social networks like Blogs, Twitter and Facebook. In view of this, it is very important to have a system that can condense the data and can extract meaningful information without human intervention. A new area of research in information retrieval (IR) has developed over the past few years called Topic Detection and Tracking (TDT). Topic detection involves detecting the occurrence of a new event such as earthquake, election results, a new movie released, or a political scam in a stream of news stories from multiple sources. Topic tracking is the process of monitoring a stream of news stories to find those that report or discuss the same event as one specified by a user. Previous approaches for Topic detection mainly focused on sources like news streams, web pages, documents, reviews and other structured and semi-structured information sources. In this thesis, we focus on detecting the underlying semantic aspects (Sub-topics) of an event and extract structured information from the sub-topics found. Topics or events on Twitter relate to major events in the real world; sub-topics on the other hand are fine-grained aspects of such events. The velocity, volume and variety with which Twitter generates text is increasing exponentially. Mining sub-topics from entities helps in trend analysis, social monitoring, topic tracking and reputation mining. In the recent past, Twitter has been widely used for spreading the social pulse about real world entities. Fresh latent sub-topics identified from Twitter feeds at any given point of time could be extremely useful in providing better topic-wise search results relevant to users’ informational needs. Also, extraction of Structured information from tweets related to a sub-topic could provide a nice summary for the subtopic. The two main challenges in mining sub-topics from tweets in real-time are (1) understanding the semantic and the conceptual representation of the tweets, and (2) the ability to determine when a new sub-topic (or cluster) appears in the tweet stream. We address these challenges by proposing two unsupervised clustering approaches. In the first approach (SSR), for each tweet, we generate a semantic space representation by keyword expansion and keyphrase identication. In the second approach (CSR), we transform each tweet into a conceptual space that represents the latent concepts of the tweet. For our evaluation, we use RepLab (CLEF) 2013 dataset. The dataset contains tweets for 61 entities. Each entity has about 700 tweets for training and 1500 tweets for testing. The SSR approach gave an F1 measure of 0.259 and CSR an F1 measure of 0.339. We show a significant increase in the F1 measure value by 16.9% as compared to the Baseline and 1% as compared to the best system in RepLab 2013, which indicates that the proposed CSR approach performs better than the state-of-the-art methods. In extension to the previous approaches, we propose a more sophisticated approach which also considers semantic similarity between concepts and a statistical way to determine a threshold for creating a new sub-topic. We initially try to detect Sub-topics from targetted entities and later try to extract structured information from them. We generate a rich semantic representation of tweets using external knowledge bases, and combine it with relevant similarity metrics to train a sub-topic detection classifier. Further, we train a Conditional Random Field (CRF) model to identify subject-predicate-object fact triplets from tweets. Comparisons with various state-of-the-art mechanisms for sub-topic detection on a dataset of 134K tweets show that the proposed approach outperforms others by a significant margin providing a best F1 score of 0.417. The proposed CRF-based fact triplets extraction approach also beats the baselines significantly providing an overall F1 of 0.43. We also try to map the extracted information to manually generated event schemas. For this task we specifically focus on the natural disaster events on twitter. As soon as natural disaster events happen, users are eager to know more about them. However, search engines currently provide a ten blue links interface for queries related to such events. Relevance of results for such queries can be significantly improved if users are shown a structured summary of the fresh events related to such queries. This would not just reduce the number of user clicks to get the relevant information but would also help users get updated with more fine grained attribute-level information. Twitter is a great source that can be exploited for obtaining su

Abstract

The huge growth in digital libraries, WWW (world wide web) and other text resources has created the demand of techniques which can work intelligently on limited linguistic resources and fulfills the growing demand of text analysis, pattern discovery and information management related operations. The graph based automated text analysis and text mining methods have received a great deal of attention in solving these issues. Actually, an important aspect of graph-based method is that it does not require deep linguistic knowledge, nor domain or language specific annotated corpora, which makes it highly portable to other domains, genres, or languages. The development of advanced graph theoretical techniques for social media mining has also enriched this area. However, the development of effective core techniques to mine the information, from text document(s) by using limited linguistic resources is a challenging task of significant interest. Still The huge growth in digital libraries, WWW (world wide web) and other text resources has created the demand of techniques which can work intelligently on limited linguistic resources and fulfills the growing demand of text analysis, pattern discovery and information management related operations. The graph based automated text analysis and text mining methods have received a great deal of attention in solving these issues. Actually, an important aspect of graph-based method is that it does not require deep linguistic knowledge, nor domain or language specific annotated corpora, which makes it highly portable to other domains, genres, or languages. The development of advanced graph theoretical techniques for social media mining has also enriched this area. However, the development of effective core techniques to mine the information, from text document(s) by using limited linguistic resources is a challenging task of significant interest. Still sincere attentions for improvements in a lot of explored core areas are required. Additionally, the exploring of unexplored/less explored areas can be very useful and key ingredient of several text mining applications. Based on the above discussed facts, we have identified some core issues (and techniques for them) like: (i) meaningful phrase identification (ii) differentiating role and sense of words, preferably via a single measure, (iii) handling information gap at the phrase level by using unsupervised scheme, (iv) integrating the importance of words as a core feature and (v) identifying group semantics and/or logically related features, (vi) sentence abstraction and so on. These techniques are very useful for multiple text mining applications like: (a) Document summarization, (b) Summarization Evaluation, (c) Document Clustering, (d) Key phrase Extraction and (e) Automatic Question Answering. The effective improvement in the results of our devised applications, over state-of-the-arts supervised, unsupervised applications, which use linguistic support and domain knowledge etc., prove the effectiveness of the proposed techniques. Our contributions related to the development in the core techniques for domain independent traditional text mining include: (i) Phrase Identification: Identifying useful phrases are still an open and challenging task, as, available linguistic and statistical state-of the art techniques, still suffer a lot of problems. The performance of several text mining tasks depends upon the quality of the identified phrases. We introduce the centrality measures based technique for phrase identification having accuracy more than 90%. We effectively apply this technique to key-phrase extraction (which is itself treated as core task for several applications like: document categorization, indexing, skimming etc.) and document clustering. (ii) Differentiating between role and sense of words: Often times words having same sense may have different roles in document(s). Neglecting such information may misguide us, especially when we compare two different texts having matching words, like: summarization evaluation, and evaluation of descriptive answers and essays, etc. We introduce the use of graph based mapping of co-occurring words and closeness centrality score for this. (iii) Reducing information gap between documents: We introduce the Wikipedia anchor text community detection based scheme, to reduce the information gap between N-grams that are conceptually-related, despite not having a match owing to differences in writing scheme or strategies. We successfully applied this scheme in document clustering. (iv)Integrating the importance of words as a core feature: Most of the traditional text mining techniques treat word/phrases as point/ “raw data” and thus ignore their importance. We believe that treating every word or phrase as a separate data point by language independent text mining techniques may be inappropriate and even known data mining techniques may not be applicable straightaway. This is becau

Abstract

One of the main challenges that prevent the large-scale deployment of Wireless Sensor Networks (WSNs) is providing the applications with the required quality of service (QoS) given the sensor nodes limited energy supplies. WSNs are an important tool in supporting applications ranging from environmental and industrial monitoring, to battlefield surveillance and traffic control, among others. Most of these applications require sensors to have a longer lifetime without human intervention and battery replacement. Therefore energy conservation is one of the main goals for implementing WSNs. To maximize the network lifetime, approaches such as duty cycling and low power listening modes have been proposed. In this thesis, I explore the possibility of further energy savings through the applying the mobility patterns in the network. In this thesis as part of my research, I propose a new mobility patterns in the network, which increase the lifetime of the network as well as reduces the random flooding of the messages in the network, thus improving the bandwidth of the entire network. Hence to validate my proposal, I conclude my thesis with the results obtained through the simulations. The simulation is carried on open source network simulator called “Network Simulator 2 (NS2)”. NS2 is popular simulator for wired, wireless network based on IEEE 802.11 and also for Wireless Sensor Network based on IEEE 802.15.4. The results obtained from the simulations closely mirror the results obtained theoretically.

Abstract

Kabaddi is a popular and an intense game played in Indian sub-continent. The key feature of the game is simultaneous embodiment of cooperation and competition among the players. In particular, the player has to implicitly or explicitly cooperate and coordinate with in a team, while competing with opponent team. The game is played on the principle - capture the raider, while not getting caught by the raider. This principle of capture sounds similar to pursuit domain, a domain used in study of multi-agent systems. There were many strategies that were proposed for pursuit domain but none of them are suitable for Kabaddi due to the game rules and constraints on field space and time. The rules and regulations of the game makes it more interesting and challenging to develop strategies for a game. The major challenges involved in the game of Kabaddi are cooperation between players, decision making by a team (which strategy to use and when), competing against the opponent team. Thus Kabaddi can provide an environment and a framework for Multi-Robot Systems and MAS researchers to evaluate strategies involving both cooperation and competition. In this thesis, we present a Kabaddi game simulator which assists the user to program strategies and evaluate them on simulated games. The Kabaddi simulator package (KSP) is built in Java and can be imported as a Java library. All the game rules of Kabaddi are incorporated into the simulator. By observing many international games, we analyzed strategies deployed by a team in various scenarios and came up with a generic solution for the game. Formations play a key role in the anti-raiders game. We introduce the concept of risk that assists the anti-raiders to get into a formation through implicit cooperation. We also use the risk factor to avoid collision among agents. Three strategies straight line formation, semi-circular formation, circular formation are developed, tested and evaluated against pursuit domain strategy. Though the intermediate goal of anti-raiders is to capture the raider they also should compete in a game. That is, the team might need to change their strategy depending upon the state of a game and must seek to increase their score. To develop a strategy that is competitive we use MDP (Markov Decision Process) which considers multiple strategies as actions and deploys them based on the state of a game. This thesis also discusses on building robots that can play Kabaddi and a few simulations of Kabaddi strategies on a robot simulator.

Abstract

The search and retrieval of relevant images and videos from large repositories of multimedia, is acknowledged as one of the hard challenges of computer science. With existing pattern recognition solutions, one cannot obtain detailed, semantic description for a given multimedia document. Several limitations exist in feature extraction, classification schemes, along with the incompatibility of representations across domains. The situation will most likely remain so, for several years to come. Towards addressing this challenge, we observe that several multimedia collections contain similar parallel information that are: i) semantic in nature, ii) weakly aligned with the multimedia and iii) available freely. For example, the content of a news broadcast is also available in the form of newspaper articles. If a correspondence could be obtained between the videos and such parallel information, one could access one medium using the other, which opens up immense possibilities for information extraction and retrieval. However, it is challenging to find the mapping between the two sources of data due to the unknown semantic hierarchy within each medium and the difficulty to match information across the different modalities. In this thesis, we propose novel algorithms that address these challenges. Different < Multimedia, Parallel Information > pairs, require different alignment techniques, depending on the granularity at which entities could be matched across them. We choose four pairs of multimedia, along with parallel information obtained in the text domain, such that the data is both challenging and available on a large scale. Specifically, our multimedia consists of movies, broadcast sports videos and document images, with the parallel text coming from scripts, commentaries and language resources. As we proceed from one pair to the next, we discover an increasing complexity of the problem, due to a relaxation of the temporal binding between the parallel information and the multimedia. By addressing this challenge, we build solutions that perform increasingly fine-grained alignment between multimedia and text data. The framework that we propose begins with an assumption that we could segment the multimedia and the text into meaningful entities that could correspond to each other. The problem then, is to identify features and learn to match a text-entity to a multimedia-segment (and vice versa). Such a matching scheme could be refined using additional constraints, such as temporal ordering and occurrence statistics. We build algorithms that could align across i) movies and scripts, where sentences from the script are aligned to their respective video-shots and ii) document images with lexicon, where the words of the dictionary are mapped to clusters of word-images extracted from the scanned books. Further, we relax the constraint in the above assumption, such that the segmentation of the multimedia is not available apriori. The problem now, is to perform a joint inference of segmentation and annotation. We address this problem by building an over-complete representation of the multimedia. A large number of putative segmentations are matched against the information extracted from the parallel text, with the joint inference achieved through dynamic programming. This approach was successfully demonstrated on i) Cricket videos, which were segmented and annotated with information from online commentaries and ii) word-images, where sub-words called Character N-Grams, are accurately segmented and labelled using the text-equivalent of the word. As a consequence of the approaches proposed in this thesis, we were able to demonstrate text-based retrieval systems over large multimedia collections. The semantic level at which we can retrieve information was made possible by the annotation with parallel text information. Our work also results in a large set of labeled multimedia, which could be used by sophisticated machine learning algorithms for learning new concepts.