Abstract

Biomolecules are the building blocks of life that regulate the biological processes within the organisms. The interplay of just three classes of biomolecules: DNA, RNA and proteins provide complexity to the biological world. Their structures, stabilities and dynamics are keys to understand the working of Nature. Advanced biophysical and biochemical techniques have proven useful to study the structure, dynamics and local flexibilities within the biomolecules. However, most of these sophisticated experimental techniques are complex and time consuming, apart from being expensive. Also, they do not always directly provide an atomistic picture of macromolecular dynamics in situ with sucient time resolution. In current scenario of enhanced computing power, computer simulations have emerged as a useful tool to not only better interpret experimental results; in several ways they complement experimental investigations. We have used simulation methods to probe some contemporary issues related to structural stability and functional dynamics of biomolecules, with focus on nucleic acids and proteins. This thesis describes investigations using simulation techniques as applied to three dierent systems, in order to address three types of issues related to biomolecular dynamics: functional behavior of purine (adenine, guanine) and lysine riboswitches; folding of small mitochondrial subunit binding protein and modeling the structure and possible functional dynamics of a drug target enzyme. The studies address a wide range of contemporary issues related to the compatibility between simulation methods used and scientific questions asked. Thus, wherever possible, the work involves benchmarking of simulation conditions and analysis methods and attempts at reconciliation of available experimental data with the interpretation of trajectory analysis results.

Abstract

Signal processing applications such as ones dealing with image/voice have an inherent capability to tolerate noise. These applications are primarily judged by human perception which can ignore certain inaccuracies in image/voice applications. Probabilistic computing is a form of computing that trades tolerable errors for large amounts of gains in terms of energy, area and speed in the underlying hardware for these applications. With the stringent requirements on energy consumption, size and processing speed through modern day computing devices, there is a need to evaluate what trade-offs can be made with respect to the quality of the application for gains in terms of energy, area and delay of the computing circuit. Motion estimation, computationally the most intensive portion of the video encoder, is a suitable candidate to be considered as an application for probabilistic computing. With a plethora of video applications that video compression caters to, motion estimation is also a widely used application necessitating research on energy, delay and area optimized circuit design for motion estimation. The focus of this research is mainly to optimize energy and processing speed of the motion estimation architecture using probabilistic computing. The term probabilistic computing encompasses various techniques out of which two have been considered in this thesis. These techniques are Probabilistic Complementary Metal Oxide Semiconductor (PCMOS) and probabilistic pruning. PCMOS is a model for CMOS emulating the erroneous nature of future technology nodes. CMOS design is continuously faced by the challenge of achieving low-energy computation, which is addressed by technology scaling accompanied by voltage scaling. Voltage scaling in turn affects the noise immunity of the device, which is predicted to result in erroneous nature of future CMOS technology nodes. The PCMOS model is used to build circuits for motion estimation algorithms. Motion estimation is established to have a high resilience towards PCMOS based computing and energy savings to the tune of 40% to 57% are seen. Furthermore, algorithmic modifications for motion estimation are suggested that further increase the achievable energy savings sizably (13% to 23% increase) at the target degradation allowed. Probabilistic pruning works towards removal of parts of the circuit that contribute least to the quality of the application, thereby, optimizing the circuit gains for tolerable amounts of error. The overall savings for motion estimation through probabilistic pruning are found to be 27% to 65% in energy, 14% to 30% in delay and 29% to 54% in area consumption of the motion estimation circuit. Probabilistic pruning is compared with bit-width reduction of the circuit for motion estimation proposed in past research. Probabilistic pruning is found to increase the processing speed via motion estimation circuit considerably (6% to 18%) for a minor increase in area consumption (3% to 5%) when compared with bit-width reduction at approximately same quality reduction and energy consumption through the motion estimation circuit.

Abstract

The amount of information available on the web is steeply increasing. We need efficient techniques to analyze such large data. Frequent itemset mining play an important role in analyzing such data. Frequent itemset mining, which extracts frequently occurring group of items, has many applications like Association rule mining, Correlations, Dimensionality Reduction, Clustering and Classification. In this thesis, we show how frequent itemsets handle the problems of evolutionary clustering and summarization of scientific articles. Evolutionary clustering is an emerging research area addressing the problem of clustering dynamic data. An evolutionary clustering should take care of two conflicting criteria: preserving the current cluster quality and not deviating too much from the recent history. We propose an algorithm for evolutionary clustering using frequent itemsets. A frequent itemset based approach for evolutionary clustering is natural and it automatically satisfies the two criteria of evolutionary clustering. We provide theoretical as well as experimental proofs to support our claims. We performed experiments on our approach using different datasets and the results show that our approach is comparable to most of the existing algorithms for evolutionary clustering. We also present a novel unsupervised approach to the problem of multi-document summarization of scientific articles, in which the document collection is a list of papers cited together within the same source article, otherwise known as a co-citation. At the heart of the approach is a Frequent Itemset based clustering which clusters fragments extracted from each co-cited article and relevance ranking using a query generated from the context surrounding the co-cited list of papers. This analysis enables the generation of an overview of common themes from the co-cited papers that relate to the context in which the co-citation was found. We present a system called SciSumm that embodies this approach and apply it on a large collection of scientific articles. We evaluate this summarization system for relevant content selection using gold standard summaries prepared on principle based guidelines. Evaluation with gold standard summaries demonstrates that our system performs better in content selection than an existing summarization system (MEAD). We present a detailed summary of our findings and discuss possible directions for future research.

Abstract

3-D medical images such as Computed Tomography(CT), Positron Emission Tomogra- phy(PET) and Magnetic Resonance Imaging(MRI) are commonly used for diagnosis. Tomo- graphic reconstruction is the underlying technique for all these images. It is often of interest to increase the resolution of these images. Some of the possible solutions for increasing the resolution are: increasing the number of detectors, changing the detector material/geometry, increasing the excitation energy level or scanning time. These solutions are limited in terms of practical implementation. Hence, nding solutions at the processing level (post data ac- quisition) is of interest. This thesis focuses on the problem of preserving details and quality of tomographic images after upsampling. We have explored two dierent approaches for generating higher resolution images. These are based on re-examining the lattice geometry for reconstruction. We oer two novel solutions, one which uses a hexagonal instead of the conventional square lattice and a second one based super resolution strategy which combines samples drawn from two lattices. In the rst solution, we reconstruct the image onto a hexagonal lattice. These samples are then interpolated to nd the samples on the desired higher resolution square lattice. In the super resolution (SR)- based solution we reconstruct the images onto 2 low resolution lattices. The lattices are rotated versions of each other which provide a 'dierent view' of an object/scene. For generating low resolution images both square and hexagonal sampling have been considered. The two solutions have been implemented and tested using a variety of test objects. These objects which are called phantoms were chosen to be of 2 types: analytical and real. Three analytically generated phantoms used were Concentric rings, dots and lines. Two real PET phantoms were Nema and Homan Brain phantoms. The results were benchmarked against upsampled images generated by: Direct upsampling and an existing super resolution technique which uses Union of Shifted Lattice (USL) samples. The evaluation results show a qualitative and quantitative improvement over results obtained by direct upsampling. The SR-based results are comparable to that obtained with USL in quality. However, the main strength of the proposed SR-based solution is the computational savings and a reduced number of required images for a given upsampling factor. i

Abstract

Previous works have used word alignments in parallel corpora to transfer information like POS tags, syntactic trees, named entities and word senses from source to target sentences. In this thesis, we worked on the problem of transferring syntactic relations from English to morphologically rich Hindi parallel text. Since the size of the parallel corpus is small and considering the presence of inflectional variations in Hindi pose data sparseness problem. We reduce these complexities to some extent using Local Word Groups (LWGs) and show their effectiveness in simplifying alignments as well as in transferring syntactic dependencies by building an alignment model with LWGs as base units and training a dependency parser on the relations projected using these LWGs. The LWG alignment model using GIZA++ scores decreases the Alignment Error Rate (AER) by 1.16 points when compared to the best GIZA++ model trained on lemmas. We also show that a dependency parser trained on the syntactic relations projected using LWGs obtained statistcal significant improvements over the relations projected using lemmas by a margin of 3.49% in terms of Unlabeled Attachment Score (UAS).

Abstract

The world of academia is growing at a tremendous rate with thousands of research papers being published every year. For a researcher looking for new dimensions of research, it is becoming an increasingly difficult task to identify the relevant yet novel domains of research from amongst the host of varied domains. There is a definite need of a system that could help the researchers in their decision making by interacting with large academic information space. Recommender systems are aimed at performing this very task. They help the researchers to overcome the information overload problem by exposing them to the most interesting results and by offering novelty, surprise and relevance. The ever-changing research fields and the increasing complexity in the relationships within the academia have therefore made such a system an essential tool in a researcher’s quest for expanding his research base. In this thesis, we propose a novel and efficient approach for author and topic recommendation to an author in a bibliographic dataset that exploits the hidden relationships in such datasets as well as addresses the issues of scalability and sparsity. Existing recommender systems largely work by creating a neighborhood of similar users and use their preferences to generate recommendations for the active user. In this thesis, we also rank the items to determine their importance in the dataset and use the ranks of the items of interest for the active user in the recommendation process. Our topic-based author recommendation algorithm aims at suggesting latent yet relevant authors to a researcher based on his research topics. For a pair of authors, their shared research interests as well as the relative diversity between their research interests forms the basis of the similarity measure in our algorithm. The objective of our topic recommendation algorithm is to suggest a set of relevant topics to a researcher based on the research interests of similar authors. The recommendation algorithm considers the importance of a topic as well as the importance of the suggesting authors to assign authoritative scores to the recommended topics. We also exploit the hierarchy of topics and their temporal property to prune the irrelevant topics for the task of recommendation. We test our algorithms on the DBLP dataset. Our experiments produced a ranked set of recommended authors and topics that on examination by field experts and based on our study were found to be relevant and fairly accurate. We study our algorithms on various parameters and validate our experiments by dividing the dataset into training and test portions. We also do a comparative study of our author and topic recommendation algorithms with popular recommendation techniques. We also discuss the system called Research Patterns built to facilitate the accessibility and visualization of the results produced by our algorithms and the possibility of extending our algorithms to other domains. Our algorithms have a host of applications like author and topic recommendation, retrieval of authors for a given topic query and vice-versa, building communities of similar authors, research paper recommendation, etc.

Abstract

The automation of activities in all areas, including business, engineering, science, and government, produces an ever-increasing stream of data. Especially, the amount of multimedia content produced and made available on the Internet, both in professional and personal collections is growing rapidly. Equally increasing are the needs in terms of efficient and effective ways to manage it. And why is that so? Because, people believe that data collected contains valuable information. But, extracting any such information/patterns is however an extremely difficult task. This has led to a great amount of research into content based retrieval and visual recognition. The most recent retrieval systems available extract low-level image features and conceptualize them into clusters. A conventional sequential scan on those image features would approximately take about a few hours to search in a set of hundreds of images. Hence, clustering and indexing forms the very crux of the solution. The state of the art uses the 128-dimensional SIFT as low level descriptors. Indexing even a moderate collection involves several millions of such vectors. The search performance depends on the quality of indexing and there is often a need to interactively tune the process for better accuracy. In this thesis, we propose a visualization-based framework and a tool which adheres to the it to tune the indexing process for images and videos. We use a feature selection approach to improve the clustering of SIFT vectors. Users can visualize the quality of clusters and interactively control the importance of individual or groups of feature dimensions easily. The results of the process can be visualized quickly and the process can be repeated. The user can use a filter or a wrapper model in our tool. We use input sampling, GPU-based processing, and visual tools to analyze correlations to provide interactivity. We present results of tuning the indexing for a few standard datasets. A few tuning iterations resulted in an improvement of over 5% in the final classification performance, which is significant. vi

Abstract

Computer aided diagnosis (CAD) using medical images is a vital outcome of application of computers in medicine. Over the years, several methods of CAD have been proposed and implemented for various pathologies and imaging modalities. In theory, CAD systems should achieve complete automation in detecting and diagnosing diseases, whereas in practice these systems aim at assisting the medical expert, for example a Radiologist, to perform effective diagnosis. CAD can also play a significant role in assisting the medical experts in public health enterprises like disease screening. Disease screening is performed by medical experts at specific community healthcare centers to detect diseases early in order to reduce the ensuing mortality and suffering. The two most prevalent applications of disease screening have been detecting retinopathy (retinal diseases) from color fundus images and breast cancer from digital mammograms. Application of CAD in such disease screening initiatives is known to produce high throughput in terms of reduction in effort, time spent and mistakes committed by the medical experts. Since screening is intended for prevention and early detection of diseases, a large number of patients arriving at the point of care turn out to be normal (no disease symptom). This poses a significant challenge for the medical expert using CAD as a large number of false alarms are detected due to the high sensitivity of disease detection in CAD systems. Therefore a significant time of the expert is spent on rejecting the false alarms during diagnosis. The large number of false alarms occurs essentially due to the difficulty in modeling various disease symptoms and normal background across images of normal and abnormal patients. This problem is further compounded due the disease centric approach of CAD where various manifestation of a disease is detected separately from the images resulting in accumulation of false alarms from each detection method. In order to address the challenges of existing CAD systems in disease screening, we propose to perform automated diagnosis in disease screening problems using a two-stage hierarchical approach. In the first stage, presence or absence of a disease is ascertained in the given image. We will refer to this stage as abnormality detection. Once the abnormality of an image is ascertained, further analysis of the disease symptom is performed for assessment of its severity, in the second stage. The abnormality detection task is treated as a normal learning problem, where only a single class corresponding to characteristics of normal medical cases are learnt. A medical case, not conforming to this normal behavior is termed as abnormal. The normal class is learnt using the global characteristics of normal medical images. The proposed approach is showcased on two disease screening problems, detection/assessment of lesions in color fundus images and classification of mammographic lesion as benign or malignant. Evaluation of our method for detection of lesions from color fundus images is performed on four publicly available image datasets. The detection performance has a sensitivity of 100 percent with specificity between 74 percent and 90 percent. Cases needing immediate referral are detected with a sensitivity of 100 percent and specificity of 97 percent. A 10-fold cross validation for lesion detection was also performed to evaluate the average detection performance. The Area Under the receiver operating characteristic Curve (AUC) ranges from 0.89 to 0.99 for various datasets. Assessment of retinal diseases into moderate and severe cases of retinopathy resulted in accuracy of 81 percent for the moderate case and 100 percent for severe cases. Lesion classification in mammograms was performed by treating benign lesions as belonging to the normal class while separating the malignant lesions by identifying them as abnormal. The sensitivity of detecting malignant lesions at 100 percent was achieved with a specificity of 97 percent. The best AUC for the lesion classification task was recorded as 0.98. The success in automated disease detection from color fundus images and mammograms establish the effectiveness of the proposed methodology.

Abstract

Recent technological advancements have led to the proliferation of uncertain data. Uncertainty is inherently present in many real world domains like images. Such databases are more complex because of the additional challenges of representing the probabilistic information. While analyzing such data, it should be handled cautiously. Traditional data-oriented techniques for analyses on uncertain data do not achieve best possible accuracy. There is a growing demand to develop efficient novel methods to handle such kind of data. Existing works on uncertain data mining are largely theoretical, where application areas are suggested but not experimented and are hypothetical. Whereas in this thesis, we present techniques and apply them in a full-fledged real-world application namely image classification and clustering. We utilize the concept of representing images in the form of a normalized model using interest points in images. This model is an uncertain-data-based adaptation of Bag of words (BoW), with each image not only represented by the visual words that it contains, but are also associated with a respective probability of occurrence in the clustered features of the image. We propose two novel algorithms for classification and clustering images which utilizes the normalized bag of words model for image representation. The uncertain associative classifier for object class identification in images (UACI) uses an Associative Classification approach to leverage latent frequent patterns in images for the identification of object classes. Unlike most image classifiers, which rely on positive and negative class sets (generally very vague) for training, UACI uses only positive class images for training. Negative class set is the set of all positive as well as negative class set. So, it is very vague and the choice of negative class set would affect the classifier. We empirically compare UACI with three other image classifiers. In our experimental evaluation, associative classification doesn’t compare well with more recent SVM based techniques like SVM-BoW-Baseline for uncertain image dataset but performed better than the BoW. Also, we propose a clustering algorithm to meaningfully group images into different categories. It uses an uncertain frequent itemset mining approach to extract the latent patterns in the form of frequent itemsets. These patterns eliminate much of the noise and represent the dominant trends which lead to a high degree of accuracy. To analyze the efficiency of this approach, we ran a set of experiments on two different datasets. This algorithm has good efficiency in generating quality clusters.

Abstract

With the daily expansion of computer network and internet applications, the risk of network related crimes are also increasing [1]. Most of the present day intrusion protection systems, security applications and antivirus software aim at detecting, and a few preventing, the damage done to end systems, at the premises where they are installed. In today’s world of rapidly paced networks, we need efficient techniques to identify the source of attacks so as to completely eliminate the malicious systems and the attacks caused by them which can benefit the entire network. Network Forensics includes the field of study which deals with techniques that aims at identifying the source of the attack. The most important part in the field of cybercrime investigation is the need to capture and store data for determining potential legal evidence and at the same time safeguard the privacy of the data plying through the network. Packet attribution systems have been used to perform trace back of the packet in the internet to its source. At the packet header level, determining the source machine from the source IP address is not an effective solution, as IP address can be altered. In order to perform trace back based on packet payload, payload attribution has to be performed at every network device through which packet traverses. This concept of payload attribution was introduced by Shan- mugasundaram et al. [2, 3]. From now throughout the remaining paper let us refer the content of packets to be queried for trace back as “excerpt”. During trace back, the excerpt has to be matched with the stored packet payload at every network device and determine the path taken by the packets. But storing the entire payload at every network device is not a practical solution due to storage and privacy concerns. Various efficient techniques based on bloom filter and its variations have been proposed until now [4]. Source Path Isolation Engine (SPIE) [5] is a payload attribution system which uses space efficient bloom filters for hashing and storing packet payload. SPIE performs repeated hashing of packets, including the invariant portion of the packet header and a part of packet payload and inserts them in Bloom Filters. These compact filters are then stored at the routers. When all routers implement SPIE, it is possible to trace back the packet to the source. The problem with SPIE is to store the packet with its non-mutable headers and a part of the payload and reconstruct the packets during trace back querying [2]. This issue is overcome by the concept of Block Bloom Filters (BBF), where the packet payload is split into blocks of certain size and hashes performed on these blocks are stored in the bloom filters. This technique has to consider all possible offset values and hence the false positive probability (FPP) increases [2]. The value of FPP can be reduced by performing attribution of hierarchies of blocks, a concept named as Hierarchical Bloom Filters (HBF) [2]. But the practical implementation of these concepts on all the routers installed in different networks and network levels increases burden on these routers in terms of processing and storage size. In this thesis, we propose a flexible environment for the implementation of these concepts and increase its practicality in the present day network devices. We put forward our analysis on certain parameters over which system administrators can analyze and take final decision on implementing these techniques on the network devices. To trace back the packet from the destination to the source, all routers in the path of the network have to implement these payload attribution mechanisms. Imposing the same implementation rules and constraints on all these routers is not practical owing to their difference in their capacity of processing and storage capabilities. Depending on the capabilities of the network device, parameters like block size, false positive probability can be adjusted to suite the situation. We have prototyped these con- cepts as software and provided experimental results for processing and storage requirements, by varying these parameters. In the later section of the thesis, we have proposed the use of attribution techniques with only the control packets that ply on the network. This information can be used to trace back vital network control information among routers like network access, session control, trafficking, etc. Our experimental results show that this approach is extremely efficient in terms of storage size and processing speeds. We then discuss our analysis on possible heterogeneous approaches which combine the idea of attributing control packets and data packets individually at every router with variable parameters to configure the bloom filter used for forensic analysis.