Nowadays we are observing an explosion of gene expression data with phenotypes. It enables researchers to efficiently identify genes responsible for certain medical condition as well as classify them for drug target. Like any other phenotype data in medical domain, gene expression data with phenotypes also suffers from being very underdetermined system. In a very large set of features but a very small sample size domain (e.g. DNA microarray, RNA-seq data, GWAS data, etc.), it is often reported that several different spurious feature subsets may yield equally optimal results. This phenomenon is known as instability. Considering these facts, we have developed robust and stable supervised gene selection algorithm to select the most discriminating non-spurious set of genes from the gene expression datasets with phenotypes. Stability and robustness is ensured by class and instance level perturbations, respectively. We have performed rigorous experimental evaluations using 10 real gene expression microarray datasets with phenotypes. It revealed that our algorithm outperforms the state-of-the-art algorithms with respect to stability and classification accuracy.

MOTIVATION: Metagenomics is the study of genetic materials directly sampled from natural habitats. It has the potential to reveal previously hidden diversity of microscopic life largely due to the existence of highly parallel and low-cost next-generation sequencing technology. Conventional approaches align metagenomic reads onto known reference genomes to identify microbes in the sample. Since such a collection of reference genomes is very large, the approach often needs high-end computing machines with large memory which is not often available to researchers. Alternative approaches follow an alignment-free methodology where the presence of a microbe is predicted using the information about the unique k-mers present in the microbial genomes. However, such approaches suffer from high false positives due to trading off the value of k with the computational resources. In this article, we propose a highly efficient metagenomic sequence classification (MSC) algorithm that is a hybrid of both approaches. Instead of aligning reads to the full genomes, MSC aligns reads onto a set of carefully chosen, shorter and highly discriminating model sequences built from the unique k-mers of each of the reference sequences. RESULTS: Microbiome researchers are generally interested in two objectives of a taxonomic classifier: (i) to detect prevalence, i.e. the taxa present in a sample, and (ii) to estimate their relative abundances. MSC is primarily designed to detect prevalence and experimental results show that MSC is indeed a more effective and efficient algorithm compared to the other state-of-the-art algorithms in terms of accuracy, memory and runtime. Moreover, MSC outputs an approximate estimate of the abundances. AVAILABILITY AND IMPLEMENTATION: The implementations are freely available for non-commercial purposes. They can be downloaded from https://drive.google.com/open?id=1XirkAamkQ3ltWvI1W1igYQFusp9DHtVl.

The closest pair problem (CPP) is an important problem that has numerous applications in clustering, graph partitioning, image processing, patterns identification, intrusion detection, etc. Numerous algorithms have been presented for solving the CPP. For instance, on n points there exists an O(n log n) time algorithm for CPP (when the dimension is a constant). There also exist randomized algorithms with an expected linear run time. However these algorithms do not perform well in practice. The algorithms that are employed in practice have a worst case quadratic run time. One of the best performing algorithms for the CPP is MK (originally designed for solving the time series motif finding problem). In this paper we present an elegant exact algorithm called MPR for the CPP that performs better than MK. Also, we present approximation algorithms for the CPP that are faster than MK by up to a factor of more than 40, while maintaining a very good accuracy.

Advances made in sequencing technology have resulted in the sequencing of thousands of genomes. Novel analysis tools are needed to process these data and extract useful information. Such tools could aid in personalized medicine. As an example, we could identify the causes for a disease by comparing the genomes of people who have the disease and those who do not have this disease. Given that human variability happens due to single nucleotide polymorphisms (SNPs), we could focus our attention on these SNPs. Investigations that try to understand human variability using SNPs fall under genome-wide association study (GWAS). A crucial step in GWAS is the identification of the correlation between genotypes (SNPs) and phenotypes (i.e., characteristics such as the presence of a disease). This step can be modeled as the k-locus problem (where k is any integer). A number of algorithms have been proposed in the literature for this problem when k = 2. In this paper we present an algorithm for solving the 2-locus problem that is up to two orders of magnitude faster than the previous best known algorithms.

Using the recent advances in sequencing technology thousands of genomes have been sequenced. This sequence data can be fruitfully employed in diagnosis, drug design, etc. Genome-wide Association Study (GWAS) focuses on this important problem of extracting useful information from genomic data. As an example, a comparison of different genomes could throw light on causes for different diseases. Human variabilities happen due to single nucleotide polymorphisms (SNPs). Thus it might suffice to focus on these SNPs while comparing different genomes. One of the important problems in GWAS is that of identifying the correlation between genotypes (SNPs for example) and phenotypes (i.e., different characteristics such as addiction, the presence of cancer, etc.) Different approaches exist for addressing this problem. One important approach is via modeling this problem as the k-locus problem (k being any integer). The case of k = 1 has been studied widely. Some algorithms also exist for solving the case of k = 2. The real cause for a disease could be more than two SNPs. The case of k > 2 has not been studied in the literature. For the first time, in this paper we present an efficient algorithm for solving the 3-locus problem that is several orders of magnitude faster than the brute force algorithm. All the software can be obtained from: engr.uconn.edu/~rajasek/ThreeLocus.

CONTACT: [email protected] or [email protected].

MOTIVATION: Next-generation sequencing techniques produce millions to billions of short reads. The procedure is not only very cost effective but also can be done in laboratory environment. The state-of-the-art sequence assemblers then construct the whole genomic sequence from these reads. Current cutting edge computing technology makes it possible to build genomic sequences from the billions of reads within a minimal cost and time. As a consequence, we see an explosion of biological sequences in recent times. In turn, the cost of storing the sequences in physical memory or transmitting them over the internet is becoming a major bottleneck for research and future medical applications. Data compression techniques are one of the most important remedies in this context. We are in need of suitable data compression algorithms that can exploit the inherent structure of biological sequences. Although standard data compression algorithms are prevalent, they are not suitable to compress biological sequencing data effectively. In this article, we propose a novel referential genome compression algorithm (NRGC) to effectively and efficiently compress the genomic sequences. RESULTS: We have done rigorous experiments to evaluate NRGC by taking a set of real human genomes. The simulation results show that our algorithm is indeed an effective genome compression algorithm that performs better than the best-known algorithms in most of the cases. Compression and decompression times are also very impressive. AVAILABILITY AND IMPLEMENTATION: The implementations are freely available for non-commercial purposes. They can be downloaded from: http://www.engr.uconn.edu/~rajasek/NRGC.zip CONTACT: [email protected].

MOTIVATION: Genome sequencing has become faster and more affordable. Consequently, the number of available complete genomic sequences is increasing rapidly. As a result, the cost to store, process, analyze and transmit the data is becoming a bottleneck for research and future medical applications. So, the need for devising efficient data compression and data reduction techniques for biological sequencing data is growing by the day. Although there exists a number of standard data compression algorithms, they are not efficient in compressing biological data. These generic algorithms do not exploit some inherent properties of the sequencing data while compressing. To exploit statistical and information-theoretic properties of genomic sequences, we need specialized compression algorithms. Five different next-generation sequencing data compression problems have been identified and studied in the literature. We propose a novel algorithm for one of these problems known as reference-based genome compression. RESULTS: We have done extensive experiments using five real sequencing datasets. The results on real genomes show that our proposed algorithm is indeed competitive and performs better than the best known algorithms for this problem. It achieves compression ratios that are better than those of the currently best performing algorithms. The time to compress and decompress the whole genome is also very promising. AVAILABILITY AND IMPLEMENTATION: The implementations are freely available for non-commercial purposes. They can be downloaded from http://engr.uconn.edu/∼rajasek/ERGC.zip. CONTACT: [email protected].

BACKGROUND: In highly parallel next-generation sequencing (NGS) techniques millions to billions of short reads are produced from a genomic sequence in a single run. Due to the limitation of the NGS technologies, there could be errors in the reads. The error rate of the reads can be reduced with trimming and by correcting the erroneous bases of the reads. It helps to achieve high quality data and the computational complexity of many biological applications will be greatly reduced if the reads are first corrected. We have developed a novel error correction algorithm called EC and compared it with four other state-of-the-art algorithms using both real and simulated sequencing reads. RESULTS: We have done extensive and rigorous experiments that reveal that EC is indeed an effective, scalable, and efficient error correction tool. Real reads that we have employed in our performance evaluation are Illumina-generated short reads of various lengths. Six experimental datasets we have utilized are taken from sequence and read archive (SRA) at NCBI. The simulated reads are obtained by picking substrings from random positions of reference genomes. To introduce errors, some of the bases of the simulated reads are changed to other bases with some probabilities. CONCLUSIONS: Error correction is a vital problem in biology especially for NGS data. In this paper we present a novel algorithm, called Error Corrector (EC), for correcting substitution errors in biological sequencing reads. We plan to investigate the possibility of employing the techniques introduced in this research paper to handle insertion and deletion errors also. SOFTWARE AVAILABILITY: The implementation is freely available for non-commercial purposes. It can be downloaded from: http://engr.uconn.edu/~rajasek/EC.zip.

Since the introduction of the Sanger sequencing technology in 1977 by Frederic Sanger and his colleagues, we observe an explosion of sequence data. The cost of storage, processing, and analyzing the data is getting excessively high. As a result, it is extremely important that we develop efficient data compression and data reduction techniques. But standard data compression tools are not suitable to compress biological data since they contain many repetitive regions. There could exist high similarities among the sequences. In this context we need specialized algorithms to effectively compress biological data. In this paper we propose novel algorithms for compressing FASTQ files. We have done extensive and rigorous experiments that reveal that our proposed algorithm is indeed competitive and performs better than the best known algorithms for this problem.

Conventional broadcasting protocols suffer from network congestion, frequent message losses and corruption of broadcast messages due to a vast number of duplicate packets transmitting in the network. In this paper, we propose an efficient, scalable and reliable broadcast protocol to send a message in the entire network where every node is guaranteed to receive the message with low overhead and minimal cost. The scalability and reliability of broadcast transmission is ensured by composing the entire network in a hierarchy of grids/squares. A higher order square is made up of four lower order squares forming a quad tree architecture. With this grid architecture a node does not need to flood the broadcast packet to the entire network. Rather a node exploits the Geographic Forwarding mechanism to send the packet to a particular square. The rest of the work is done by the very first node receiving the packet destined for that particular grid. This node has now the responsibility to update its own grid with the broadcast packet. The whole procedure is repeated iteratively in every grid. Simulation results show that our proposed algorithm is reliable, scalable, robust and also outperforms some other promising broadcasting protocols that exist in the current literature.

Determining point to point traffic matrix is essential for Internet service providers (ISPs) in carrying out traffic engineering tasks for network management and planning purposes. However, it is very difficult and costly to measure this traffic matrix directly. Hence, traffic matrices are inferred from link measurements through estimation, using different techniques. There are different techniques for this traffic matrix estimation and there is still a need for evaluating these existing techniques. Some of those techniques have been previously compared, but with new improved techniques recently developed there is a need to revisit the comparisons. In this paper, we have carried out studies to compare three very popular methods: the tomogravity, the entropy maximization and linear programming methods. We find that the tomogravity method best estimates the traffic matrix among the methods we tested. We then incorporate some enhancements which improve this method. Specifically we established that knowing some point to point traffic may improve the estimation but not necessarily, and this is counter-intuitive. We modify the existing entropy maximization method by adding more constraints and we find that our modified method outperforms the existing entropy maximization and tomogravity methods.