Abstract

Copy number variations, a type of structural variations, contribute most to the variability between human genomes. CNVs play an important role in human evolution, adaptability to environmental factors and disease susceptibility. The development of next generation sequencing technologies has enabled researchers to identify CNVs at a very high resolution like never before. Several methods have been proposed to identify CNVs leveraging the advantages offered by NGS data. However, there is still scope of improvements. We have developed a depth of coverage based CNV detection pipeline called integrated platform for Copy number variations Detection, Annotation and Visualisation (iCopyDAV), which gives users the option of choosing a method from multiple methods at every stage of the pipeline. The pipeline provides an end-to- end solution starting from pre-treatment of raw alignment data to variant calling, annotation and visualization. A comprehensive comparative analysis of our pipeline carried out revealed that the total variation minimization (TVM) method resulted in accurate detection of small CNVs <5kbp at >30x coverage with very low breakpoint errors. TVM showed precision 1 at sequencing depths >20x and had the best F-score at all depths except at 50X. iCopyDAV high precision score makes it a reliable tool to detect CNVs from NGS data. Using TVM approach in iCopyDAV we performed a population level study of chromosome 11 of five South Asian, one European, one East Asian and one African populations, considering twenty samples from each population. Copy number variant regions (CNVRs) constructed for each population, were used in multivariate analysis to study population stratification. Structural features such as tandem repeats, segmental duplications etc., spanning CNVRs were analyzed. Functional annotations such as genes, enhancers, long non-coding RNA and miRNA binding sites etc., spanning the CNVRs were studied. Gene ontology and pathway enrichment analysis of the genes associated with detected CNVRs were performed. Diseases associations of CNVRs were also analyzed in our studies. Our analysis of chromosome 11 with respect to all the aforementioned features of detected CNVRs did not reveal any population-specific trends, suggesting a need for carrying such CNV analysis for all the chromosomes.

Abstract

Services provided for the flow of network packets varies based on network requirements of a user. Such a differentiation is termed as Quality of Service. In the modern day internet, with the evolution ofreal time applications which require video/audio streaming and high bandwidth, there is an ever growing demand for quality of service. With such high demand for QoS, there have been multiple methodologies to make it scalable and more usable in the current day network. Two such QoS provisions are Differentiated QoS and Integrated QoS. Differentiated services are used to make the application of QoS more scalable. On the other hand, Integrated services have a requirement of reserving the resources pertaining to a complete path in advance. Thereby, this restricts usage of resources by other entities making integrated services approach less scalable. However, the aforementioned services are applied to the packets within an access network, in order to avoid computation and complexity in the backbone network. This thesis suggests architectural approaches, which, when applied to the packets, serves the QoS requirements beyond their access network into the backbone network. Our approach has an analogy to the road network, which tries to solve the road accident problems. The mechanism of such an architecture is discussed, in which routers with a mapping algorithm play a key role. The placement of such routers in diverse backbone architectures has been explained. The thesis also suggests economic solutions for the proposed infrastructure to explain the feasibility of the architecture. This research also explores the possibilities and mechanisms to be followed in order to extend the QoS in the backbone networks. It explains the consequences of the proposal and has deliberations onthe various possible scenarios in which the proposed architecture might be helpful. It also presents a simulation of an SDN network using mininet and packet captures depicting the extension of QoS outsidethe access networks are also presented.

Abstract

It has been extensively argued that there are two distinct processes governing behaviour: Goal Directed and Habitual. There have been multiple attempts at establishing a mechanism that governs which behaviour should be in charge of making sequential decisions leading to a distant reward. This thesis is organized in three parts. First we explore a simple task of action selection in a rather complex bio-physical model of Basal Ganglia. We implement a probabilistic inference task and show that the model learns to establish a representation of reward contingencies. We then implement a model of Parkinson’s disease for patients with and without medication as an exploration of how the disease and its drug might act in Basal Ganglia. Next, we move on to complex sequential tasks and present a framework that unifies three distinct dichotomies: Goal Directed versus Habitual behaviour, Explicit versus Implicit Learning and Model-Based versus Model-Free Reinforcement Learning. This framework suggests a hierarchical organization of each mechanism of the dichotomies in two forms: first, we suggest that the Goal-Directed controller plays a dominant role in behaviour which is then taken over by habitual behaviour across multiple trials as the chunk size increases. Second, we suggest that the most granular actions are executed habitually whereas more abstract level actions are goal directed. We suggest that a goal directed behaviour occurs with the engagement of attention as opposed to habitual behaviour which is more automatic, thereby linking the dichotomy to Explicit versus Implicit learning. We then present the idea that behaviour or execution can be organized in opposite directions to each other with attention playing a role of theswitch. The final part is a computational implementation of the unified theory presented previously. We show that a hierarchical organization of Goal-Directed and Habitual Behaviour implemented using Model-Based and Model - Free Reinforcement Learning is successfully able to fare well against the respective pure forms and that such an organization is suitable for explaining motor skill acquisition. We present a possible functional network of interacting brain areas in the frontal cortex with the final values of states and actions represented in the striatum – following which the Basal Ganglia model explored earlier could be used to perform action selection. We implement the Parkinson’s model in simulations of a grid world and suggest a qualitative parallel with the observed literature.

Abstract

Indian languages are morphologically rich and free word order languages. There are many other distinguished characteristics possessed by them. Keeping these in mind Computational Paninian Grammar formalism was chosen to represent the syntacto-semantic relations between different words in a sentence and establish their relationship with the verb, for these languages. The syntactico-semantic dependency relations and their labels defined in the CPG formalism are very fine grained to account for the rich grammatical functions. The number of distinct dependency labels are 82 as per the scheme (both interchunk and intrachunk). It has been observed that the more semantically oriented annotation schemes make labeled parsing more difficult than the schemes based on more surface-oriented grammatical functions. These relations can be organised in the form of a hierarchical structure with each level representing a degree of granularity which can be underspecified. We aim to explore whether reducing granularity of these labels can help bridge the gap between between Labeled Score and Unlabeled Attachment Score. Universal Dependencies (UD) on the other hand have a coarser scheme of grammatical representation. We extend UD to Indian languages through conversion of Paninian Dependencies to UD for the Hindi Dependency Treebank (HDTB) and observe the effects of a relatively sparse taxonomy. We discuss the differences in annotation in both the schemes, present parsing experiments for both the formalisms and empirically evaluate their weaknesses and strengths for Hindi. We produce an automatically converted Hindi Treebank conforming to the international standard UD scheme, making it useful as a resource for multilingual language technology. Indian language treebanking was undertaken to create resources for facilitating data driven syntactic analysis. The annotations in Indian Languages’ treebanks are generally multi-layered and furnish information on part of speech category of word forms, their morphological features, related word groups and the syntactic relations. Rich syntactic features are very important for building state-of-the-art syntactic analysers but they require lot of feature engineering expertise. These indicative features pose the problem of data sparsity, incompleteness and expensive extraction. Building expensive tools to automatically generate these features is an expensive task. Keeping this in mind our work proposes to apply non linear neural network for parsing five resource poor Indian Languages belonging to two major language families – Indo-Aryan and Dravidian. Bengali and Marathi are Indo-Aryan languages whereas Kannada, Telugu andMalayalam belong to the Dravidian family. The non linear architecture elegantly addresses all the problems mentioned above. While little work has been done previously on Bengali and Telugu linear transition-based parsing, we present one of the first parsers for Marathi, Kannada and Malayalam. All the Indian languages are free word order and range from being moderate to very rich in morphology. Therefore in this work we propose the usage of linguistically motivated morphological features ( suffix and postposition ) in the non linear framework, to capture the intricacies of both the language families. We also capture chunk and gender, number, person information elegantly in this model. We put forward ways to represent these features cost effectively using monolingual distributed embeddings. Instead of relying on expensive morphological analyzers to extract the information, these embeddings are used effectively to increase parsing accuracies for resource poor languages. Our experiments provide a comparison between the two language families on the importance of varying morphological features. Part of speech taggers and chunkers for all languages are also built in the process.

Abstract

In this thesis, we extensively study the problem of broadcasting of entanglement. We first introduce the elements of quantum information theory and then define various kinds of quantum and classical correlations. We also talk about various measures to quantify correlations, which are important in the context of broadcasting correlations. Next, we re-conceptualize the idea of state dependent quantum cloning machine, and in that process, we introduce different types of state dependent cloners like static and dynamic state dependent cloners. We derive the conditions under which we can make these cloners independent of the input state. Our main motivation for defining various types of cloning machines is that if we have partial information about the state to be cloned beforehand, we can choose the best performing cloner. In the broadcasting part, as our resource initial state, we start with general two qubit state and consider specific examples like, non maximally entangled state (NME), Werner like state (WLS), and Bell diagonal state (BDS). We apply both state dependent and state independent cloners, both locally and non-locally, in each of these cases. Incidentally, we find several instances where state dependent cloners outperform state independent cloners in broadcasting. This work gives us a holistic view on the broadcasting of entanglement in various two qubit states, when we have an almost exhaustive set of cloning machines in our arsenal.

Abstract

Sparse matrix computations such as multiplying a sparse matrix with a sparse matrix, denoted spmm, and multiplying a sparse matrix with a dense matrix, denoted csrmm, are fundamental operations in linear algebra that have several applications. Hence, efficient and scalable implementations of spmm and csrmm have been a topic of immense research. Efforts are aimed at implementations on FPGAs, multi-core architectures, GPUs and such emerging computational platforms. The architectural trend towards heterogeneity has pushed heterogeneous computing to the fore of parallel computing research. Owing to the highly irregular nature of spmm and csrmm it is observed that CPUs and GPUs can offer comparable performance (Lee et al. [26]) and hence implementations on CPU+GPU systems are widely researched. In this thesis, we propose Sorted-Workqueue, a CPU+GPU heterogeneous algorithm for spmm and csrmm based upon Workqueue framework proposed by Kothapalli et al. [25]. We perform experiments on general sparse matrices from standard datasets and study the performance of spmm and csrmm. Another trend towards customizing algorithms according to characteristics of the input are gaining research interest in recent times. In this thesis, we consider real-world sparse matrices that exhibit scale-free nature and exploit their characteristics to propose better algorithms for spmm and csrmm. Focusing on such matrices, we propose novel algorithms HH-CPU for spmm and HD-CPU for csrmm on a CPU+GPU heterogeneous platform. We perform experiments on a wide variety of real-world scale-free matrices from standard datasets and show performance improvement over the state-of-art algorithms on CPU+GPU heterogeneous platform. A majority of the heterogeneous algorithms follow a work partitioning approach where the input is divided into appropriate sized pieces so that individual computing units can process the “right” pieces of the input. Such a division is done by means of some parameters, usually thresholds which vary for each input instance. However, identifying the right value of the threshold is usually non-trivial and may require an extensive empirical search. Such an extensive empirical search may potentially offset any gains accrued out of heterogeneous algorithms. We also show that one of our proposed method, HH-CPU, requires some thresholds to be computed in order to identify the right work that can be assigned to the right processor. For this, we propose a simple, yet effective technique based on sampling which can adapt to the algorithm used, the input instance and the heterogeneous computing units in the platform. Our technique is generic in its applicability as we will demonstrate in this thesis. We validate our technique on HH-CPU and show that we can find the required threshold ± 7.5% away from the best possible threshold.

Abstract

This thesis proposes the development of an FPGA prototype to estimate the direction of arrival for adaptive array antenna based on matrix pencil technique.With the passage of time, there is need for more data rates however due to the limitation of natural frequency we have to look for other alternatives. Therefore, people have started other ways to increase the frequency like angle, code, geographical space, etc. In this thesis, we will be concentrating on angle dimension. In estimating Direction of Arrival (DOA), the most important step is to calculate the eigenvalues of matrix. Literature survey reveals that limited work has been carried out to compute the eigenvalues of an asymmetric matrix from implementation perspective. Therefore a new approach to calculate the eigenvalues of matrix has been described. In this work we present a method to estimate the DOA, known as Matrix Pencil which is a key technique to estimate the DOA for adaptive array antenna for cellular wireless base stations. This thesis describes the hardware implementation of Matrix Pencil on FPGA. Matrix Pencil uses QR algorithm for the calculation of eigenvalues which is the most critical part of the system. In order to accelerate and increase the efficiency of the system it utilises Triangular Systolic Array (TSA) architecture to compute the eigenvalues of the system. Matrix Pencil is found to yield better results than its peer algorithms like MUSIC, ESPIRIT. When processing have to be performed in coherent environment and when there is small number of snapshots available. The power consumed by the design is 0.65W. Maximum frequency which can be achieved by the system is 900MHz. Latency of our design is 2.7 mS which is approximately 28 times faster than general purpose computer based solution.

Abstract

Code-switching is a phenomenon of mixing grammatical structures of two or more languages under varied social constraints. The code-switching data differ so radically from the benchmark corpora used in NLP community that the application of standard technologies to these data degrades their performance sharply. Unlike standard corpora, these data often need to go through additional processes such as language identification, normalization and/or back-transliteration for their efficient processing. In this thesis, we investigate these indispensable processes and other problems associated with syntactic parsing of code-switching data and propose methods to mitigate their effects. In particular, we study dependency parsing of code-switching data of Hindi and English multilingual speakers from Twitter. We present a treebank of Hindi-English code-switching tweets under Universal Dependencies scheme and propose domain adaptation techniques to efficiently leverage monolingual syntactic annotations and the annotations from the Hindi-English code-switching treebank. Firstly, we propose modifications to the parsing models which are trained only on the Hindi and English monolingual treebanks. We have shown that code-switching texts can be efficiently parsed by the monolingual parsing models if they are intelligently manipulated. Against an informed monolingual baseline, our parsing strategies are at-least 10 LAS points better. Secondly, we propose a neural stacking model for parsing that efficiently leverages part-of-speech tag and syntactic tree annotations in the code-switching treebank and the monolingual Hindi and English treebanks. We also present normalization and back-transliteration models with a decoding process tailored for code-switching data. Our neural stacking models achieve an accuracy of 90.53% for POS tagging and 80.23% UAS and 71.03% LAS for dependency parsing. Results show that our neural stacking parser is 1.5% LAS points better than the augmented parsing model and our decoding process improves results by 3.8% LAS points over the first-best normalization and/or back-transliteration.

Abstract

We demonstrate the effectiveness of an end-to-end trainable hybrid CNN - RNN architecture in recog- nizing Urdu text from printed documents, typically known as Urdu OCR , and from Arabic text embedded in videos and natural scenes. When dealing with low-resource languages like Arabic and Urdu, a major adversary in developing a robust recognizer is the lack of large quantity of annotated data. We overcome this problem by synthesizing millions of images from a large vocabulary of words and phrases scraped from Wikipedia’s Arabic and Urdu versions, using a wide variety of fonts downloaded from various online resources. Building robust recognizers for Arabic and Urdu text has always been a challenging task. Though a lot of research has been done in the field of text recognition, the focus of the vision community has been primarily on English. While, Arabic script has started to receive some spotlight as far as text recognition is concerned, works on other languages which use the Nabatean family of scripts, like Urdu and Persian, are very limited. Moreover, the quality of the works presented in this field generally lack a standardized structure making it hard to reproduce and verify the claims or results. This is quite surprising considering the fact that Arabic is the fifth most spoken language in the world after Chinese, English, Spanish and Hindi catering to 4.7% of the world’s population, while Urdu has over a 100 million speakers and is spoken widely in Pakistan, where it is the national language, and India where it is recognized as one of the 22 official languages. In this thesis, we introduce the problems related with text recognition of low-resource languages, namely Arabic and Urdu, in various scenarios. We propose a language independent Hybrid CNN - RNN architecture which can be trained in an end-to-end fashion and prove it’s dominance over simple RNN based methods. Moreover, we dive deeper into the working of its convolutional layers and verify the robustness of convolutional-features through layer visualizations. We also propose a method to synthe- size artificial text images to do away with the need of annotating large amounts of training data. We outperform previous state-of-the-art methods on existing benchmarks by quite some margin and release two new benchmark datasets for Arabic Scene Text and Urdu Printed Text Recognition to instill interest among fellow researchers of the field.

Abstract

Large scale emergencies are part of life that can require mass evacuations. Planning for such emergencies is an important component of traffic management to minimize any losses arising due to them. As human cognitive behaviour plays an important role during response to emergencies, understanding such cognitive behavior will help us plan better. The cognitive behavior of each individual driver agent may include greed (hurry), mob mentality and other unexpected biases which may slowdown the clearing up of traffic. To provide an efficient solution to this problem, we study the effect of human cognitive behaviors on traffic patterns during an emergency situation. We make the assumption that during the emergency, there are traffic police or other personnel trying to guide the vehicles so that the traffic clearance is sped up (to minimize the human or property losses), as they have a global view of the emergency and have accurate real-time updates. Another assumption is that the traffic police use the Ford-Fulkerson Algorithm, which is a standard algorithm to perform an efficient evacuation using flow model, to maximize the flow in the (traffic) network and then perform an extensive agent based analysis to study the traffic patterns that arise due to a variety of human factors and biases. While human biases can cause disruption to plans generated by the Ford Fulkerson algorithm, there are situations where we may want encourage behaviors such as greed. For example, we may want an ambulance to reach its destination at the earliest possible time hence would like it to display a greedy behavior. This implies that different vehicles may need to have different priorities. Current evacuation models, including Ford-Fulkerson and other known algorithms, overlook such a scenario, and treat all the vehicles as same. To overcome this drawback, we also focus on the problem of prioritized routing of vehicles without affecting the overall evacuation time. Prioritized routing may happen even during normal times, but it becomes even more important during emergencies, as emergency vehicles, police vehicles and large vehicles (such as buses) that carry a lot of people need to have a higher priority in terms of evacuation. To summarize, we study the following two problems in this thesis: (a) How human biases effect plans made for emergency evacuation (b) Incorporate priority of vehicles when generating plan for evacuation. Through a series of experiments performed using the well-known traffic simulator SUMO, we make the following contributions: (a) We validate that Ford-Fulkerson Algorithm is indeed efficient for clearance of vehicles in case of non-prioritized evacuation (b) Driver agents that do not follow the specified directions due to their preferences and biases lose out on an average (c) In line with our expectations, we find that having a prior knowledge and/or real-time updates about the environment can indeed offset the effect of human biases to a good extent. (d) We map the prioritized routing problem to the minimum-cost maximum-flow problem, a standard problem formulation in network flow theory. (e) We then develop the Prioritized Routing Assistant for Flow of Traffic (PRAFT) that casts the prioritized routing problem which includes a notion of priority of vehicles and priority of routes into the minimum cost maximum flow problem. (f) Through a series of experiments performed using the well-known traffic simulator SUMO, we could establish that PRAFT indeed maps higher priority vehicles to better quality routes and is monotonic in the sense that decreasing priority order of vehicles maps to a decreasing route quality.