Motivation: The rapid development of sequencing technology has led to an explosive accumulation of genomic data. Clustering is often the first step to be performed in sequence analysis. However, existing methods scale poorly with respect to the unprecedented growth of input data size. As high-performance computing systems are becoming widely accessible, it is highly desired that a clustering method can easily scale to handle large-scale sequence datasets by leveraging the power of parallel computing. Results: In this paper, we introduce SLAD (Separation via Landmark-based Active Divisive clustering), a generic computational framework that can be used to parallelize various de novo operational taxonomic unit (OTU) picking methods and comes with theoretical guarantees on both accuracy and efficiency. The proposed framework was implemented on Apache Spark, which allows for easy and efficient utilization of parallel computing resources. Experiments performed on various datasets demonstrated that SLAD can significantly speed up a number of popular de novo OTU picking methods and meanwhile maintains the same level of accuracy. In particular, the experiment on the Earth Microbiome Project dataset (∼2.2B reads, 437 GB) demonstrated the excellent scalability of the proposed method. Availability and implementation: Open-source software for the proposed method is freely available at https://www.acsu.buffalo.edu/~yijunsun/lab/SLAD.html. Supplementary information: Supplementary data are available at Bioinformatics online.

MOTIVATION: Sequence analysis is arguably a foundation of modern biology. Classic approaches to sequence analysis are based on sequence alignment, which is limited when dealing with large-scale sequence data. A dozen of alignment-free approaches have been developed to provide computationally efficient alternatives to alignment-based approaches. However, existing methods define sequence similarity based on various heuristics and can only provide rough approximations to alignment distances. RESULTS: In this article, we developed a new approach, referred to as SENSE (SiamEse Neural network for Sequence Embedding), for efficient and accurate alignment-free sequence comparison. The basic idea is to use a deep neural network to learn an explicit embedding function based on a small training dataset to project sequences into an embedding space so that the mean square error between alignment distances and pairwise distances defined in the embedding space is minimized. To the best of our knowledge, this is the first attempt to use deep learning for alignment-free sequence analysis. A large-scale experiment was performed that demonstrated that our method significantly outperformed the state-of-the-art alignment-free methods in terms of both efficiency and accuracy. AVAILABILITY AND IMPLEMENTATION: Open-source software for the proposed method is developed and freely available at https://www.acsu.buffalo.edu/∼yijunsun/lab/SENSE.html. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The rapid development of sequencing technology has led to an explosive accumulation of genomic sequence data. Clustering is often the first step to perform in sequence analysis, and hierarchical clustering is one of the most commonly used approaches for this purpose. However, it is currently computationally expensive to perform hierarchical clustering of extremely large sequence datasets due to its quadratic time and space complexities. In this paper we developed a new algorithm called ESPRIT-Forest for parallel hierarchical clustering of sequences. The algorithm achieves subquadratic time and space complexity and maintains a high clustering accuracy comparable to the standard method. The basic idea is to organize sequences into a pseudo-metric based partitioning tree for sub-linear time searching of nearest neighbors, and then use a new multiple-pair merging criterion to construct clusters in parallel using multiple threads. The new algorithm was tested on the human microbiome project (HMP) dataset, currently one of the largest published microbial 16S rRNA sequence dataset. Our experiment demonstrated that with the power of parallel computing it is now compu- tationally feasible to perform hierarchical clustering analysis of tens of millions of sequences. The software is available at http://www.acsu.buffalo.edu/∼yijunsun/lab/ESPRIT-Forest.html.

We conduct an extensive experimental evaluation of a class of WiFi active power/energy consumption models for smartphones that are based on parameters readily available to the upper layers of the protocol stack. We first consider a number of parameters used by previous models and show their limitations. We then focus on a recent approach modeling the active power consumption as a function of the application layer throughput. We study the properties of a previously proposed throughput-based model in relation to other parameters such as the packet size and/or the transport layer protocol, and we evaluate its accuracy under a variety of scenarios that have not been considered in previous studies. Our results show that the model works well in a number of scenarios, with both 802.11nand 802.11ac-equipped smartphones, and its accuracy can be largely improved with the knowledge of transport layer protocol and packet size. However, such knowledge makes the model more complex and results in largely reduced accuracy in high throughput settings or on hardware different from the one that was used for training. We further discuss a few practical issues related to the measurement and modeling methodology.

The rapid development of sequencing technology has led to an explosive accumulation of genomics data. Clustering is often the first step to perform in sequence analysis, and hierarchical clustering is one of the most commonly used approaches for this purpose. However, the standard hierarchical clustering method scales poorly due to its quadratic time and space complexities stemming mainly from the need of computing and storing a pairwise distance matrix. It is thus necessary to minimize the number of pairwise distances computed without degrading clustering performance. On the other hand, as high-performance computing systems are becoming widely accessible, it is highly desirable that a clustering method can be easily adapted to parallel computing environments for further speedup, which is not a trivial task for hierarchical clustering. We proposed a new hierarchical clustering method that achieves good clustering performance and high scalability on large sequence datasets. It consists of two stages. In the first stage, a new landmark-based active hierarchical divisive clustering method was proposed that partitions a large-scale sequence dataset into groups, and in the second stage, a fast hierarchical agglomerative clustering method is applied to each group. By assembling hierarchies from both stages, the hierarchy of the data can be easily recovered. Theoretical results showed that our method can recover the true hierarchy with a high probability under some mild conditions and has a linearithmic time complexity with respect to the number of input sequences. The proposed method also facilitates an efficient parallel implementation. Empirical results on various datasets showed that our method achieved clustering accuracy comparable to ESPRIT-Tree and ran faster than greedy heuristic methods.

Cognitive radio networks (CRNs) have emerged as a promising solution to the ever-growing demand for additional spectrum resources and more efficient spectrum utilization. A large number of routing protocols for CRNs have been proposed recently, each based on different design goals, and evaluated in different scenarios, under different assumptions. However, little is known about the relative performance of all these protocols, let alone the tradeoffs among their different design goals. In this paper, we conduct the first detailed, empirical performance comparison of three representative routing protocols for CRNs, under the same realistic set of assumptions. Our extensive simulation study shows that the performance of routing protocols in CRNs is affected by a number of factors, in addition to PU activity, some of which have been largely ignored by the majority of previous works. We find that different protocols perform well under different scenarios, and investigate the causes of the observed performance. Furthermore, we present a generic software architecture for the experimental evaluation of CRN routing protocols on a testbed based on the USRP2 platform, and compare the performance of two protocols on a 6 node testbed. The testbed results confirm the findings of our simulation study.

We conduct the first detailed measurement study of the properties of a class of WiFi active power/energy consumption models based on parameters readily available to smartphone app developers. We first consider a number of parameters used by previous models and show their limitations. We then focus on a recent approach modeling the active power consumption as a function of the application layer throughput. Using a large dataset and an 802.11n-equipped smartphone, we build four versions of a previously proposed linear power-throughput model, which allow us to explore the fundamental trade off between accuracy and simplicity. We study the properties of the model in relation to other parameters such as the packet size and/or the transport layer protocol, and we evaluate its accuracy under a variety of scenarios which have not been considered in previous studies. Our study shows that the model works well in a number of scenarios but its accuracy drops with high throughput values or when tested on different hardware. We further show that a non-linear model can greatly improve the accuracy in these two cases.

Cognitive radio networks (CRNs) have emerged as a promising solution to the ever-growing demand for additional spectrum resources and more efficient spectrum utilization. A large number of routing protocols for CRNs have been proposed recently, each based on different design goals, and evaluated in different scenarios, under different assumptions. However, little is known about the relative performance of all these protocols, let alone the tradeoffs among their different design goals. In this paper, we conduct the first detailed, empirical performance comparison of three representative routing protocols for CRNs, under the same realistic set of assumptions. Our extensive simulation study shows that the performance of routing protocols in CRNs is affected by a number of factors, in addition to PU activity, some of which have been largely ignored by the majority of previous works. We find that different protocols perform well under different scenarios, and investigate the causes of the observed performance. Furthermore, we present a generic software architecture for the experimental evaluation of CRN routing protocols on a test bed based on the USRP2 platform, and compare the performance of two protocols on a 6 node test bed. The test bed results confirm the findings of our simulation study.