Abstract

A read-only transaction (ROT) does not modify any data. The main issues regarding processing of read-only transactions (ROTs) are correctness, data currency and performance. Even though the popular two-phase locking protocol processes ROTs correctly with no data currency related issues, its performance deteriorates with data contention. To improve the performance of ROTs, snapshot isolation-based approaches have been proposed. Eventhough snapshot isolation-based approaches improve the performance of ROTs, both data currency of ROTs andcorrectness (serializability) are compromised. In this paper, we propose an asynchronous speculative locking protocol (called as ASLR) which improves the performance ofROTs by trading extra processing resources. The simulation results show that ASLR improves the performance of ROTs significantly over two-phase locking and snapshot isolation-based approaches with manageable extra processing resources. The ASLR approach processes ROTs without any data currency and correctness issues.

Abstract

A read-only transaction (ROT) does not modify anydata. Efforts are being made in the literature toimprove the performance of ROTs without correct-ness and data currency issues. The widely used two-phase locking protocol (2PL) processes the transac-tions without any correctness and data currency issues.However, the performance of 2PL deteriorates withdata contention. Snapshot isolation (SI)-based pro-tocols proposed in the literature improve the perfor-mance of ROTs, but they compromise on correctnessand data currency issues. Speculative locking (SL)protocols are proposed in the literature for improv-ing the performance of ROTs by carrying out spec-ulative executions only for ROTs and following 2PLfor update transactions. In SL-based protocols, up-date transactions are blocked if they conflicting withROTs. In this paper, we have proposed an improvedapproach to improve parallelism among update trans-actions and ROTs by exploiting a new notion called“compensatability”. In this protocol, an ROT whichcan be “compensatable” can complete the executionand carry out compensating operation to incorporatethe effect of conflicting update transactions. As aresult, the parallelism is improved over SL protocolsas the update transactions which are conflicting with‘compensatable’ ROTs need not block. In this paper,we have proposed a protocol by exploiting both “com-pensatability” property of ROTs and speculation. Thesimulation results show that the proposed protocol im-proves the performance by carrying out less number ofspeculative executions. Further, the proposed protocoldoes not violate serializability criteria.

Abstract

Prokaryotic Genomes undergo various mutational events during the course of genome evolution through a variety of processes including Horizontal Gene Transfer. These regions of about 10 - 100 Kb in length are called Genomic Islands and presence of such regions offers selective advantage to the organism and may aid in the organism's growth, survival (saprophytic or symbiotic mode) or display of pathogenicity. Earlier analysis on horizontally transferred regions has shown significant variations from the average genomic values in their GC content, codon preferences and dinucleotide bias. We have developed a web-based tool identifying genomic islands in prokaryotic genomes (GIPro) based on various measures, viz., GC content (total and at individual codon positions), dinculeotide biases, and biases in codon and amino acid usage, carried out in a sliding window analysis along the length of the genome. The regions that deviate by n standard deviations (n - user defined, default value 2) from the average genome values for at least two measures are identified as probable genomic islands by the tool. GIPro can also be used for comparison of user defined regions / gene sets to confirm whether both belong to the same genome or have differences in their dinucleotide or codon usage biases as a result of horizontal transfer.

Abstract

Identifying tandem repeats in the proteome of any organism is important not only for understanding the structure and function of the proteins but also for analyzing the association of abnormal expansion of repeat regions with disorders We have developed an efficient tool for identifying Peptide Periodic Repeats (PEPPER) in protein sequences. The tool has three in-built modules: In the first module, initial screening of the protein sequence by a uni-dimensional vector equivalent to the dot-matrix is used to identify all possible repeat regions. In the second module, a sliding window analysis of the putative repeat region using a K-tuple identifies the period and the possible pattern of the repeat. In the third module, wraparound dynamic programming (WDP) algorithm is implemented to obtain the exact repeat boundaries. If the protein sequence does not contain tandem repeat region, then the second and third steps of the algorithm are skipped making it computationally efficient for database search compared to the other existing algorithms. We report up to three possible multiple-periodicities in a given repeat region. The tool reports the consensus repeat pattern, the complete repeat region, the score and alignment of the consensus with the repeat region along with percentage mismatch/indels. A preliminary comparison of our results with the TRIPS database of protein tandem repeats showed that our program not only identifies all the repeats in the TRIPS database, but we were also able to re-annotate a few incorrectly annotated repeats and found few new repeats no reported in the TRIPS database. PEPPER provides the user the facility to change parameter values for identifying small or approximate tandem repeats. A database of repeats can be built by the user for his set of protein sequences on the fly with PEPPER.

Abstract

About 14% of the protein sequences in the Swissprot database contain repetitive region, viz., tandem repeats, multiple copies of motifs/profiles, multiple copies of domain. And eukaryotic proteins are more likely to have repeats than Bacteria and Archaea. Our main focus is only on tandem repeats. Tandem repeat can be defined as contiguous repeat pattern of two or more copies. These copies can be exact or approximate. Many proteins with these repeat are involved in functions like transcription, translation, protein-protein interaction. Proteins with tandem repeats are involved in various neurodegenerative diseases like Huntington's disease. These proteins are also found to occur in sequences which are poorly conserved in evolution. We have developed a database of tandem repeats in protein sequences: Protein Tandem Repeats DataBase(PTRDB). The data for this database is extracted using our in-house tool PEPPER, a tool for identifying PEPtide PEriodic Repeats. This database is built on SwissProt (ver 51.7). PTRDB have 3145 proteins with 4713 tandem repeats. 77.74% are found in Eukaryota, 16.63% in Bacteria and 0.67% in Archaea. About 5% of proteins in this database are associated with disease. We have classified the database organism wise. This database can be queried by various attributes like SwissProt ID, organism name, PDBID, repeat pattern, repeat length, keyword and copy number. It gives the detail information of tandem repeats like SwissProt ID (hyperlinked to SwissProt to give Fasta sequence), organism name, PDBID (hyperlinked to PDB), one line description of the protein, gene name, protein name, taxonomy ID (hyperlinked to EBI), Family information (hyperlinked to Pfam), Description of associated disease, OMIM ID, scoring matrix with gap extension for the repeat, repeat pattern with alignment score, copy number, repeat length, start point, end point, alignment of repeat pattern with repeat region, secondary structure information of the repeat region. With the increasing abundance of tandem protein repeats in various proteomes this database will be increasingly important in proteome comparison.

Abstract

Recently much attention is being focused on the analysis of the three dimensional structure of proteins using graph and network concepts. The simplest protein network graph is constructed by defining the amino acids as nodes and the edges drawn between amino acids (within a threshold) which attempt to capture not only covalent but also non-covalent interactions. Analysis of the topological details of proteins with known structures, such as clustering of specific types of amino acids important for structure, folding and function, is of great value and is an active field of research. Since structures of a large number of proteins is now available, automatic methods of analysis are required to analyze them and recently, the tools from graph theory are being explored for such analysis. Here, we propose to use graph properties and their spectral analysis for identifying patterns in protein structures, in particular, structural repeats or motifs. These repeats are not easily detectable at the sequence level because of low conservation or high divergence between independent repeated units. The importance of such repeats in understanding biological function resides not only in their high frequency among known sequences, but also in their abilities to confer multiple binding and structural roles on proteins, e.g., zinc finger domain, a constituent of transcription factors involved in DNA binding, where the composition and copy number of individual tandem repeats confers selectivity and activity of DNA binding. This functional versatility is apparent not only among different repeat types, but also for similar repeats from the same family. Our understanding of repeats, with respect to their structures, functions, and evolution, therefore represents a considerable challenge. Our analysis of the degree distribution and spectral analysis of a set of proteins from various repeat families show that the repeat regions exhibit similar connectivity patterns in the graph. The network property, Betweenness, was found to identify accurately the repeat boundaries in protein families. Thus, this approach can help in identifying repeated motifs in proteins which are difficult to identify at the sequence level.

Abstract

In this paper we consider the problem of extracting the spe-cial properties of any given record in a dataset. We are interested in determining what makes a given record unique or different from the ma-jority of the records in a dataset. In the real world, records typically represent objects or people and it is often worthwhile to know what spe-cial properties are present in each object or person, so that we can make the best use of them. This problem has not been considered earlier inthe research literature. We approach this problem using ideas from clus-tering, attribute oriented induction (AOI) and frequent itemset mining.Most of the time consuming work is done in a preprocessing stage and the online computation of the uniqueness of a given record is instantaneous

Abstract

The problem of search and retrieval of images using relevance feedback has attracted tremendous attention in recent years from the research community. A real-world-deployable interactive image retrieval system must (1) be accurate, (2) require minimal user-interaction, (3) be efficient, (4) be scalable to large collections (millions) of images, and (5) support multi-user sessions. For good accuracy, we need effective methods for learning the relevance of image features based on user feedback, both within a user-session and across sessions. Efficiency and scalability require a good index structure for retrieving results. The index structure must allow for the relevance of image features to continually change with fresh queries and user-feedback. The state-of-the-art methods available today each address only a subset of these issues. In this paper, we build a complete system FISH - Fast Image Search in Huge databases. In FISH, we integrate selected techniques available in the literature, while adding a few of our own. We perform extensive experiments on real datasets to demonstrate the accuracy, efficiency and scalability of FISH. Our results show that the system can easily scale to millions of images while maintaining interactive response time.

Abstract

An important problem in biological data analysis is to pre-dict the family of a newly discovered sequence like a pro-tein or DNA sequence, using the collection of available se-quences. In this paper we tackle this problem and presentREBMEC, a Repeat Based Maximum Entropy Classifier of biological sequences. Maximum entropy models are known to be theoretically robust and yield high accuracy,but are slow. This makes them useful as benchmarks to evaluate other classifiers. Specifically, REBMEC is based on the classical Generalized Iterative Scaling (GIS) al-gorithm and incorporates repeated occurrences of subse-quences within each sequence. REBMEC uses maximal frequent subsequences as features but can support other types of features as well. Our extensive experiments on two collections of protein families show that REBMEC performs as well as existing state-of-the-art probabilistic classifiers for biological sequences without using domain-specific background knowledge such as multiple align-ment, data transformation and complex feature extraction methods. The design of REBMEC is based on genericideas that can apply to other domains where data is orga-nized as collections of sequences.

Abstract

In this paper, we present RBNBC, a Repeat Based Naive Bayes Classifier of bio-sequences that uses maximal fre-quent subsequences as features. RBNBC’s design is based on generic ideas that can apply to other domains where the data is organized as collections of sequences. Specifically,RBNBC uses a novel formulation of Naive Bayes that incor-porates repeated occurrences of subsequences within each sequence. Our extensive experiments on two collections of protein families show that it performs as well as existing state-of-the-art probabilistic classifiers for bio-sequences.This is surprising as it is a pure data mining based generic classifier that does not require domain-specific background knowledge. We note that domain-specific ideas could fur-ther increase its performance.