Abstract

The primary mRNAs or the pre-mRNAs frequently undergo splicing that involves excision of intron sequences and ligation of the coding exon sequences. Across tissues and conditions, within an individual plant and animal, the splicing can occur in more than one way for a pre- mRNA giving rise to alternative mRNA transcripts (isoforms/splice forms). It is known that such alternative splicing is the major mechanism of producing the diversity across the transcriptomes and/or proteomes of tissues using the same genome (Nilsen and Graveley, 2010). Specific short sequences of nucleotides forming the splice sites and regulatory motifs are located in the introns and exons and such 'motifs' can be used to select or de-select a specific type of intron-excision and exon-ligation. Thus, the motifs can act as enhancers or silencers of splicing. A number of studies revealed that pre-mRNA sequences also harbor structurally identifiable elements in vivo that may regulate splicing. Using such motifs and structural features, the cells seem to splice the pre-mRNAs in multiple ways. Various splice-events seem to have evolved to increase the protein repertoire of the cell. Conventional types of alternative splicing mechanisms are exon skipping, alternative 3‘and 5‘ splice sites, intron retention, mutually exclusive exons, alternative promoters and alternative poly adenylation (A) sites. While many studies have indicated the relative frequency of different types of splice events, more specific studies are warranted, specifically to study their frequency across differently expressed tissues in mammals, even under normal conditions. The analysis of motifs in the context of different type of splice events is particularly at a very preliminary stage for every species/group. Hence, the current study attempts to exploit recently established sets of tissue-specific and ubiquitously transcribed genes to compare the types of alternative splicing-events, and then explore the possible sequence and structural features across the major types of events. The presence of these RNA secondary structures is usually predicted in silico by computational programs like Mfold, RNAfold, RNAStructure, Sfold, etc and are confirmed by in vitro (by biochemical methods) and in vivo (by small scale experiments and mutational analysis) studies. Though very little is understood regarding their role in alternative splicing, the studies indicate that pre-mRNAs, being highly flexible in nature forms secondary structures (e.g. stem loop structures), whichare likely to play role in inclusion/exclusion of a particular exon(s), or in selection of 5‘ splice sites or 3‘ splice sites (donor or acceptor) and thus determine the variety of transcript-isoforms. In our attempt to understand structures of pre- mRNAs that play a role in alternative splicing events of human, mouse and rat species, we have extracted published information on 30 mammalian genes for which pre-mRNA secondary structural analysis was done either in silico or in vitro or in vivo. Exon skipping events involving cassette exons are the predominant type of alternative splicing (Ast, 2004). Earlier studies showed that 74% alternative splicing events are tissue specific (Wanget al, 2008). However, evaluating the distribution of tissue specific/cell type/developmental stage specific splice-events has not been easy for researchers despite the huge amount of genome- & transcriptome-wide experimental data. With the aim to understand tissue specific splice-events, a comparative analysis was performed in the current study on alternative splice events of 200 genes belonging to testis exclusive and ubiquitously expressed sets, obtained from MGEx-Tdb (Acharya et al, 2010). This analysis showed that apart from exon skipping, alternative promoter driven splice events are enriched in the testis exclusive genes. Alternative 5‘ and 3‘ splice sites comprise moderately abundant splice-events. Thus the results indicate that at genes expressed preferentially in different tissues show varied frequencies of splice-events and thereby generate the protein diversity. Our data also reveals that intra-exon deletions, along with intron retention, mutually exclusive events and alternative poly adenylation (A) sites, also form the minor splice-events across the tissues. With the aim to identify splice-event specific motifs, sequence analysis was performed. A distinct set of 3‘ ends of introns of cassette exons and constitutive exons were used for this purpose. Occurrence and distribution of experimentally proven human branch point motifs were analyzed across the intron-exon junctions. Though there is no significant difference in the arrangement of branch point motifs, the study discovered a few novel motifs found within 100 nucleotide length intron-exon junctions of cassette and constitutive exons. A specific novel motif of 19 bases length is particularly interesting as it i

Abstract

Due to the recent advances in the networking capabilities, individual users and organizations are willing to use online services to store and process their data. Many image searching applications use external servers to store their huge image data for providing online services such as image searching. But images being sensitive data, we need to ensure that the privacy of the database and all communicating parties are kept intact. Firstly we need to ensure the database’s security with respect to the server. Secondly, no meaningful information about the end user’s query is to be revealed to the server. Simultaneously, the server should not reveal any information other than the query results to the user. Classical Oblivious transfer protocols are capable of ensuring both the user and the server privacy as well in such cases. They allow a sender to transfer one of potentially many pieces of information to a receiver, but remains oblivious as to what piece has been transferred. But, these protocols are practically usable only if the amount of information being queried is of small size. However, for image transfer, in their original form, an oblivious transfer protocol is highly inefficient due to its huge communication overhead. In this scenario, we consider the novel problem of oblivious retrieval of similar images from an outsourced database server. We employ SIFT descriptors to process the image data. We compute the similarity between two images based on a threshold set on the distance between the obtained features. To conduct such computations, the server must usually know the inputs from the user. However, when there is no trust on the server, privacy will be a major concern for the user. This problem is referred to as secure multiparty computation(SMC) in literature. We have developed three secure distance protocols, using the concepts of SMC, with varied efficiencies based on the privacy requirements they meet. In the first and second protocols, we achieved a constant computational complexity of O(k) in terms of homomorphic operations and a linear communication complexity of O((M + N)k). In the third protocol, we achieved a constant computational complexity of O(k + m) whereas a communication complexity of O((M + N)(k + m) + MN) is achieved. The extra overhead involved in this protocol however is due to the additional privacy requirements it offers. Traditional encryption algorithms such as data encryption standard, have the weakness of low-level efficiency while encrypting large data such as images. So, to ensure security of the data on the server effectively, we use a light weight non-linear chaotic algorithm to store the images in encrypted format. They have the advantages of high-level security and large key space while maintaining acceptable efficiency. Based on these concepts, we have designed a working prototype and tested the protocol on a database of 9000 real-life images. We employed the techniques of Paillier encryption schemes in our secure distance protocols. In our protocol, the overall computation takes three rounds of communication between the client and the server. Our results show a reasonable trade-off on the image query time, when compared to the privacy requirements being satisfied.

Abstract

Ability to autonomously navigate from a start to a given goal configuration while satisfying certain requirements or constraints is at the kernel of almost every robotic applications. Whether it’s a repetitive pick and place operation in the confines of industry assembly lines or a car driving by itself in urban or off-road scenario, robotic systems are required to have the ability to autonomously plan its motions and consequently the inputs to its actuators. Such functionality in robotic systems require software or a set of algorithms which dictates the motion of the robot’s actuators depending on its perception of the environment and its location in the environment. Motion planning in robotics is the problem of developing such software or set of algorithms and is considered to be one of the fundamental problems in robotics research The proposed thesis deals with motion planning problem with differential inequality and equality constraints. The evolution model of the wheeled mobile robots are usually described as differential equality constraints. Whereas higher level requirements are modelled as differential inequality constraints. For example stability requirements for a wheeled mobile robot operating on uneven terrains can be represented as set of differential inequalities. Similarly the collision avoidance requirements for a robot operating in dynamic environments are also modelled as differential inequality constraints. In this thesis we propose computationally efficient methodologies for computing the solution space of differential constraints. We show that we are able to obtain a characterization of solution spaces by just solving a set of low dimensional linear and quadratic inequalities. Consequently we build on top of this result and propose incremental sampling based planners as well as trajectory optimization approaches for motion planning. At the secondary level, we also make contributions to some specific aspects of motion planning on uneven terrain and in dynamic environments. For example existing works on uneven terrain navigation are based on planar or point mass evolution model of the robot. In the current thesis we present the methodology to deduce the 3D evolution of the robot on uneven terrain. We also present a novel concept called Feasible Acceleration Count which acts as an unified metric for quantifying the stability of the robot on uneven terrain as well as the efficiency of the incremental sampling based planners on producing stable trajectories on uneven terrain. We also present a novel concept called time scaled collision cone which is path constrained version of the collision cone concept used to characterize the set of collision avoidance manoeuvres in dynamic environments. We show that time scaled collision cone constrains can be solved in closed form and forms the crux of the proposed motion planning framework for dynamic environments.

Abstract

Structural complexity theory deals with the study of complexity classes, their internal structure and the relationships which exist among the classes. The class P^{SAT} is the class of all languages which can be decided by a deterministic polynomial time Turing machine with oracle access to SAT oracle. By limiting the number of available queries as a resource, we can consider subsets of P^{SAT}. Here, P^{SAT[f(n)]} is the class of all languages which can be decided by a deterministic polynomial time Turing machine with oracle access to f(n) queries to SAT oracle. If the queries are asked in parallel, the class is called P^{SATp[f(n)]}. While the question of whether non-determinism brings any advantage to a deterministic polynomial time Turing machine is the famous P vs NP question, another interesting question one can ask is whether any problem which can be decided with oracle access to two queries to an NP oracle can be decided by one query to an NP oracle. Since SAT is NP-complete, the question is framed as P^{SAT[1]} vs P^{SAT[2]}. The polynomial hierarchy (PH) is one of the most well-known structures in structural complexity theory and it contains the classes P, NP, coNP as well as generalizations of these classes at different levels. The polynomial hierarchy is conjectured to have infinite levels. On the contrary, if the polynomial hierarchy happens to top out at a particular level, then it is no longer infinite and is said to collapse to that particular level. The class P^{SAT} is one of the classes that lie between the first and second levels of the polynomial hierarchy and so do the classes P^{SAT[1]} and P^{SAT[2]}. One way to think about the P^{SAT[1]} vs P^{SAT[2]} question is to look at the implications which arise while assuming that both the classes are equal. The assumption that one query to a SAT oracle is as powerful as two queries to a SAT oracle is referred to as the 'two queries assumption'. There are many implications of the two queries assumption, P^{SAT[1]}=P^{SAT[2]}, and the topic is a well-researched area. This most profound implication of the two queries assumption is the collapse of the polynomial hierarchy with several efforts bringing down the collapse to subsequently lower levels. We explore the implications of the two queries assumption, P^{SAT[1]}=P^{SATp[2]}, with respect to the polynomial hierarchy (PH) and Arthur-Merlin classes (AM and MA). We prove the following results under the assumption P^{SAT[1]}=P^{SATp[2]}: 1) AM = MA 2) There exists no relativizable proof for PH is a subset of AM 3) Every problem in PH can be solved by a non-uniform version of a Arthur-Merlin(AM) protocol where Arthur(the verifier) has access to one bit of advice. 4) PH = P^{SAT[1]MA[1]} and PH = P^{SAT[2],pr(MA Intersection coMA)[1]}) ( Here 'pr' refers to a promise version of the class) The first results shows the equivalence of the classes MA and AM under the two queries assumption. Under the two queries assumption, Chakaravarthy and Roy showed that PH collapses to their newly defined class NO_2^P Intersection YO_2^P. The second results shows the impossibility of a relativizable proof for PH being a subset of AM which we show by means of a relativized world where coNP is not a subset of MA but the two queries assumption holds. Since NP is a subset of MA which in turn is a subset of NO_2^P unconditionally, this result shows the impossibility of a relativizable collapse to MA=AM. This result also improves upon the result by Buhrman and Fortnow that we cannot show that PH is a subset of NP under the two queries assumption using relativizable proof techniques. Though a relativizable proof showing that PH is a subset of AM is not possible, we show a containment of PH in a non-uniform variant of AM where the verifier has access to one bit of advice. This relativizable result is our third result. Our fourth result shows that any problem in PH can be simulated by a deterministic polynomial-time Turing machine with one query to an NP oracle and one query to an MA oracle. This can also be done by a deterministic polynomial-time Turing machine with two queries to an NP oracle and one query to a pr(MA Intersection coMA) oracle. These two results imply that simulating MA in a P^{SAT[1]} machine is as hard as collapsing PH to P^{SAT[1]}, if the two queries assumption is assumed to be true. These two results are incomparable to the other best known results on the collapse of the polynomial hierarchy under the two queries assumption to NO_2_P Intersection YO_2_P and ZPP^{SAT[1]}.

Abstract

Natural Language Interface to Database (NLIDB) systems allow the users to query databases in a natural language. A NLIDB system takes a natural language (NL) query as input from the user and converts it to a database query language like SQL (structured query language). In this work, we present a novel approach to design a generic, portable and contextual NLIDB system. We have designed a novel computational paninian grammar (CPG) framework based semantic frames (i.e. domain knowledge) to identify the domain terms in the NL query. We propose a novel graph based method to identify join conditions of the SQL query. By using our approach, the domain of a NLIDB system can be easily changed without disturbing the implementation details of the system. Our approach greatly reduces both the size of the domain knowledge required to develop a NLIDB system and the time to create the domain knowledge. We propose a novel approach to identify contextual information in NLIDB systems. We present a novel classification of the interactions between user and system: Strongly Coherent interaction, Coherent interaction and Weakly Coherent interaction. We proposed three models depending on the way in which the contextual information can be utilized in the interactions: Linear Disjoint Model, Linear Coincident Model and Non-Linear Model. We propose a relationship schema among the responses (user and system responses). Further, we also present a novel method to identify contextual information in Linear Disjoint interactions. We evaluated our approach on university related queries and the results confirm the viability of the proposed approach.

Abstract

The Internet and its applications have increased to an enormous extent in the past decade. This has exposed its users to various threats. In-premise appliances such as firewalls, IDS and anti-virus usually just prevent the attack and do not trace the attacker. Network forensic techniques can be used to traceback the source and the path of an attack that can be used as a legal evidence in a court of law. Packet attribution is a network forensics method that can be used to perform traceback of the packet to its source. It does not rely upon header of IP packet alone because headers can be spoofed and manipulated. Hence for accurate traceback, there is a need to include packet‘s payload to perform attribution. Storing each and every packet traversing though network is not practical and would raise privacy concerns. Packet Attribution System technique which stores the network data in compressed formats is more suitable for such applications. Given a payload (or its significant portion/signature called excerpt) and time interval, attribution system would enable identifying receivers and senders of the packet. During traceback, the excerpt needs to be matched with the stored packet payload at every network device and identify the path taken by the packets. Various compression techniques based on Bloom Filters were proposed to solve both storage and privacy issues. Packet Attribution Systems like Source Path Isolation Engine, Block Bloom Filters, and Hierarchical Bloom Filters are based upon bloom filters to traceback the attack path. Existing techniques have defined a way to store and query the bloom filters, but have not provided a standard mechanism to submit the excerpt query to the routers. Because there is no common way for submitting the query, it would lead to implementation difficulties. In this thesis, we propose query approach, leveraging existing standards and techniques based on SNMP; it is easy to implement and deploy at each router using standard SNMP extensions. All the features inherently supported by SNMP can be used including security features of SNMPv3 while performing excerpt query. In this approach, a new Management Information Base (MIB) is defined to capture all the query attributes. Router’s SNMP agent is extended by loading the new MIB implementation. NMS or a MIB Browser can be used (without any modifications) by simply loading extended MIB structure and send SNMP request to router for the excerpt. This approach can be used not only by Packet Attribution Systems, but also by any approach which involves submitting excerpt query to the network appliances. In case of incident, NMS sends the excerpt query to all the routers in Autonomous System (AS). Each router upon receiving the request, search their bloom filters for existence of excerpt and send the result to NMS. NMS receives the response from different routers and determines the traceback path from victim to source of attack. Here all the routers are engaged in searching the bloom filters while causing possible latency in performing actual routing tasks; this degrades network performance and in-turn may lead to self Denial of Service (DoS) on the network. To avoid the performance issue, in this thesis, we propose the optimization of routers to be searched, by prioritizing them. In this method, as a first step we sequentially search only the preferred routers in the path and traceback the attacker. Routers to be searched will be determined by modified packet attribution methods and communicated to NMS while performing excerpt query. There would be no need to calculate the attack path and only required routers will be loaded to determine attack path.

Abstract

Syntactic parsing is the process of analyzing a given natural language sentence to identify various syntactic roles played by the words in the sentence. Such roles can be very useful for downstream natural language processing applications. Parsing morphologically rich languages is a challenging task due to their non-configurational properties like long distance dependencies, free word order, non-projective structures and complex agreement rules. Dependency parsing using computational panianian grammar was succesfully tried for Hindi, which is a morphologically rich, relatively free-word-order language compared to English. Both rule based and data-driven dependency parsers for Hindi exist and are being used in some downstream applications (like Machine Translation). Rulebased techniques operate on expert rules and constraints manually loaded into the algorithm that detect the relationships between the words. Data-driven techniques, on the other hand, exploit the available manually annotated parse trees using various machine learning techniques, to learn a mapping between the sentences and the parse trees. While rule-based systems work as expected on the sentence types they can handle, they often suffer from lesser coverage than data-driven systems. This leads to data-driven systems achieving better accuracies than rule-based systems across different types of data. However, the existing rule-based technique (constraint-based parsing) for Hindi dependency parsing exploits the notion of a clause in sentences while doing parsing thereby distributing the parsing complexity into two stages instead of a one stage parsing strategy that is employed in the data-driven techniques. In this work, we use insights from the constraint based parsing framework to develop a two-stage data-driven clausal dependency parsing approach for Hindi. We first propose a data-driven method to do clausal parsing (parsing different clauses in a sentence separately). To use the partial parses thus obtained in a full sentence dependency parser, we propose two data-driven methods that can start with a partial parse (instead of starting from a raw sentence) and completes the full dependency parse. We compare each of these methods in their ability to deal with different issues in statistical parsing of morphologically rich languages. These methods lead to a statistically significant improvement over the state-of-the-art Hindi dependency parsing accuracy for sentences with more than one clause (complex sentence). Detailed error analysis was carried out to sort out the constructions for which the best dependency parsers (for Hindi) till now perform well and the constructions for which, the parsers have to be improved significantly.

Abstract

Since FCC had authorized UWB frequency range from 3.1 GHz to 10.6 GHz for wireless communication, several technologies developed for communication applications. And, demand of low cost, high data rate wireless communication systems rapidly increased. Although, current wireless design circuits built for cellular or non-cellular applications, trade-off with matching, signal detection, linearity, gain and noise parameters. In wireless receiver systems, effect of noise of all the subsequent stages is reduced by the gain of low noise amplifier (LNA) and its noise injects directly into the receiver. Thus, it is necessary to boost the desired signal power while adding as little noise and distortion as possible so that the retrieval of this signal is possible in the later stages in the system. As LNA is first block in receiver chain, it must provide high gain for the next blocks. Moreover, noise of LNA is critical, since the received input signal is extremely weak and can be easily corrupted by even small amount of thermal noise. Additionally, it is desirable to integrate the circuit with CMOS technology to achieve low cost and chip area. This block has the job of matching the antenna input with the rest of the circuitry and simultaneously amplifying it for further processing. Recent demonstrations show that LNAs ranging from few MHz to 10 GHz are included in wireless receivers which uses single LNA for contiguous broadband signal processing. And, there are various techniques to design narrow band and wide band LNAs such as design using basic common source and common gate configurations with few improvement methods such as using noise cancellation techniques. In contrast to existing LNA topologies implementing noise cancellation techniques which usually do not consider much about gain improvement, this work proposes a design of common gate LNA employing a noise cancelling technique which not only reduces the noise but also improves the gain and is novel to best of our knowledge. In order to cancel the dominant thermal noise, we have analyzed the noise contributions from both, active and passive components in an existing CG LNA. The input matching device viz. first CG transistor was identified as the most dominant noise source which contributes 42% of overall LNA noise and remains flat i.e. (2.8 ± 0.3) dB over the entire range. However, second stage common source transistor contributes 22% in whole range and is more near the corner frequencies which is due to the narrow band characteristics of common source amplifiers. Hence, this work’s target is to cancel the most dominant thermal noise through proposed noise cancelling technique. The proposed technique is based on combining two paths one with reversed phase noise-signal and the other with non-reversed phase noise-signal, simultaneously the RF-signals in the two paths should be in-phase. The two parallel paths were designed by symmetrical cascade combination of CG-CS and CS-CG stages. Moreover, theoretical model of noise cancellation is presented along with the derived equations of overall noise figure. Finally, implementation is done using TSMC 0.18 μm CMOSRF technology on Cadence Spectre RF tool. Significantly, proposed LNA achieve a reduction of 22.49% in base noise figure and 31.48% improvement in peak power gain when compared to LNA without noise cancelling technique. Ultimately, peak power gain of 28.4 dB and base NF of 3.17 dB with good stability and linearity are achieved over the spectrum from 2.5 GHz to 4.5 GHz. Additionally, this work implement a design of UWB LNA which include interstage matching network to carry forward desired signal with the stoppage of undesired signal. Also includes a Chebyshev band pass filter for input matching and a shunt-series inductive peaking network to compensate the gain roll-off at higher frequencies. This design provides a peak power gain of 17.12 dB and base noise figure 3.4 dB within the frequency range from 3.1 GHz to 10.6 GHz. Also demonstrate a good input matching i.e. well below -10 dB in the desired frequency range. The entire circuit consumes 11.2 mW with 1.8 V supply and occupies 1 mm x 0.9 mm of layout area. Moreover, a detailed survey of various existing methodologies (basic and advanced) for narrow band, wide band and noise cancelling LNAs are discussed with their pros and cons.

Abstract

Barter was the original means of exchange and commerce in the olden days and was replaced by currency in the modern world. However, with the growth of ecommerce and the advent of the internet, online trade exchanges have sprouted. This has resulted in a spurt of online trading activity in the form of auctions, B2B and C2C barter. Hand-to-hand barter has given way to multifarious online trade exchanges such as BizXchange, BarterCard and Swap.com. Currently, one of the largest networks of online trade is BarterCard with over 50 million dollars of annual worldwide trade. In our work, we have explored a new and unstudied trade market which is a trust-based local, deadline-driven community. This trade market is explained below. Herein, the participants are members of a close-knit community such as a university hostel or a gated community. In a small social environment such as the ones mentioned, ordinary people are expected to have a variety of needs arising from time to time. Often, objects are required for short periods of time (a book to read), one-time use (redcolored shoes for a theme party) and the person is unwilling to buy new items for one-time use from the market. In such cases, the most common solution people opt for, is to borrow things from friends. We have explored and extended this trend to a larger community wherein close friends expand their barter circle to local acquaintances. Participants behave as ‘givers’ and ‘takers’ who exchange goods with each other over a period of time. The concept of ‘utility’ has been defined for both givers and takers in the following manner.

Abstract

Separation of images into its constituent components based on source of data, frequency distribution, or nature of data has been a widely used technique in the field of image processing and computer vision. Many problems are solved by partitioning images into components and working on each component separately. Common examples include breaking down of image into Red, Green and Blue channels/components for ease of representation or into Luminance and Chrominance for better compression. In this thesis, we explore the separation of natural images into appropriate components for the purpose of representation as well as recognition. We first introduce a framework where separation of images into direct and global components helps in modeling of 3D textures. These 3D textures are often described by parametric functions for each pixel, that models the variation in its appearance with respect to varying lighting direction. However, parametric models such as Polynomial Texture Maps(PTMs) tend to smoothen the changes in appearance. Therefore we propose a technique to effectively model natural material surfaces and their interactions with changing light conditions. We show that the direct and global components of an image have different characteristics, and when modeled separately, leads to a more accurate and compact model of the 3D surface texture. Direct component is mainly affected by structural properties of the surface and is therefore deals with phenomena like shadows and specularity, which are sharply varying functions. The global component is used to model overall luminance and color values, a smoothly varying function. For a given lighting position, both components are computed separately and combined to render a new image. This method models sharp shadows and specularities, while preserving the structural relief and surface color. Thus rendered image have enhanced photorealism as compared to images rendered by existing single pixel models such as PTMs. We then look at separating an image based on its sources of illumination or albedo variations for the purpose of scene text segmentation. Extracting text from scene images is a challenging task due to the variations in color, size, and font of the text and the results are often affected by complex backgrounds, different lighting conditions, shadows and reflections. A robust solution to this problem can significantly enhance the accuracy of scene text recognition algorithms leading to a variety of applications such as scene understanding, automatic localization and navigation, and image retrieval. We propose a method to extract and binarize text from images that contains complex background. We use Independent Component Analysis (ICA) to map out the text region, which is inherently uniform in nature, while removing shadows, specularity and reflections, which are included in the background. The technique identifies the text regions from the components extracted by ICA using a simple global thresholding method to isolate the foreground text. We show the results of our algorithm on some of the most complex word images from the ICDAR 2003 Robust Word Recognition Dataset and compare with previously reported methods.