•Fast assembly of large and complex metagenomic datasets up to hundreds of Gb.•Integration of advanced assembly practices gives better assembly quality.•CPU-based algorithms eliminate GPU-dependency, ...yet more memory-efficient and faster.
The study of metagenomics has been much benefited from low-cost and high-throughput sequencing technologies, yet the tremendous amount of data generated make analysis like de novo assembly to consume too much computational resources. In late 2014 we released MEGAHIT v0.1 (together with a brief note of Li et al. (2015) 1), which is the first NGS metagenome assembler that can assemble genome sequences from metagenomic datasets of hundreds of Giga base-pairs (bp) in a time- and memory-efficient manner on a single server. The core of MEGAHIT is an efficient parallel algorithm for constructing succinct de Bruijn Graphs (SdBG), implemented on a graphical processing unit (GPU). The software has been well received by the assembly community, and there is interest in how to adapt the algorithms to integrate popular assembly practices so as to improve the assembly quality, as well as how to speed up the software using better CPU-based algorithms (instead of GPU).
In this paper we first describe the details of the core algorithms in MEGAHIT v0.1, and then we show the new modules to upgrade MEGAHIT to version v1.0, which gives better assembly quality, runs faster and uses less memory. For the Iowa Prairie Soil dataset (252Gbp after quality trimming), the assembly quality of MEGAHIT v1.0, when compared with v0.1, has a significant improvement, namely, 36% increase in assembly size and 23% in N50. More interestingly, MEGAHIT v1.0 is no slower than before (even running with the extra modules). This is primarily due to a new CPU-based algorithm for SdBG construction that is faster and requires less memory. Using CPU only, MEGAHIT v1.0 can assemble the Iowa Prairie Soil sample in about 43h, reducing the running time of v0.1 by at least 25% and memory usage by up to 50%. MEGAHIT v1.0, exhibiting a smaller memory footprint, can process even larger datasets. The Kansas Prairie Soil sample (484Gbp), the largest publicly available dataset, can now be assembled using no more than 500GB of memory in 7.5days. The assemblies of these datasets (and other large metgenomic datasets), as well as the software, are available at the website https://hku-bal.github.io/megabox.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UL, UM, UPCLJ, UPUK, ZRSKP
A simple, reliable method for identifying β‐lactoglobulin (β‐LG) in dairy products is needed to protect those with β‐LG allergies. A common, practical strategy for target detection is designing ...simplified nucleic acid nanodevices by integrating functional components. This work presents a label‐free modular β‐LG aptasensor consisting of an aptamer‐loop G‐quadruplex (G4), the working conformation of which is regulated by conformational antagonism to ensure respective module functionality and the related signal transduction. The polymorphic conformations of the module‐fused sequence are systematically characterized, and the cause is revealed as shifting antagonistic equilibrium. Combined with conformational folding dynamics, this helped regulate functional conformations by fine‐tuning the sequences. Furthermore, the principle of specific β‐LG detection by parallel G4 topology is examined as binding on the G4 aptamer loop by β‐LG to reinforce the G4 topology and fluorescence. Finally, a label‐free, assembly‐free, succinct, and turn‐on fluorescent aptasensor is established, achieving excellent sensitivity across five orders of magnitude, rapidly detecting β‐LG within 22‐min. This study provides a generalizable approach for the conformational regulation of module‐fused G4 sequences and a reference model for creating simplified sensing devices for a variety of targets.
Conformational regulation aided by antagonism enables an β‐lactoglobulin (β‐LG) aptamer‐loop G‐quadruplex (G4) sensor. The tailored β‐LG aptamer is fused with the G4 module to form an aptamer‐G4 sequence. The conformational study reveals conformational antagonism that resulted in the polymorphic conformation of the sequence. The parallel G4 serves as the functional conformation for specific β‐LG detection.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SAZU, SBCE, SBMB, UL, UM, UPUK
Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic traceability, and in this paper, we study the class of bounded clique-width graphs through the lens of ...succinct data structures. A data structure is said to be succinct if the amount of space used by the data structure is information-theoretically optimal up to lower-order additive terms. More specifically, we design a succinct data structure for graphs on n vertices whose clique-width is at most k≤ϵlogn for some constant 0<ϵ<1/6, that supports degree, adjacency, and neighborhood queries efficiently. This resolves an open problem of Kamali (Algorithmica-2018). As an application of our main technique, we also propose succinct data structures for distance-hereditary and Ptolemaic graphs, which are subclasses of the class of graphs with clique-width at most 3.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The state-of-the-art performance for several real-world problems is currently reached by deep and, in particular, convolutional neural networks (CNN). Such learning models exploit recent results in ...the field of deep learning, leading to highly performing, yet very large neural networks with typically millions to billions of parameters. As a result, such models are often redundant and excessively oversized, with a detrimental effect on the environment in terms of unnecessary energy consumption and a limitation to their deployment on low-resource devices. The necessity for compression techniques able to reduce the number of model parameters and their resource demand is thereby increasingly felt by the research community. In this paper we propose the first extensive comparison, to the best of our knowledge, of the main lossy and structure-preserving approaches to compress pre-trained CNNs, applicable in principle to any existing model. Our study is intended to provide a first and preliminary guidance to choose the most suitable compression technique when there is the need to reduce the occupancy of pre-trained models. Both convolutional and fully-connected layers are included in the analysis. Our experiments involved two pre-trained state-of-the-art CNNs (proposed to solve classification or regression problems) and five benchmarks, and gave rise to important insights about the applicability and performance of such techniques w.r.t.the type of layer to be compressed and the category of problem tackled.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
5.
Parallel construction of succinct trees Fuentes-Sepúlveda, José; Ferres, Leo; He, Meng ...
Theoretical computer science,
11/2017, Volume:
700
Journal Article
Peer reviewed
Open access
Succinct representations of trees are an elegant solution to make large trees fit in main memory while still supporting navigational operations in constant time. However, their construction time ...remains a bottleneck. We introduce two parallel algorithms that improve the state of the art in succinct tree construction. Our results are presented in terms of work, the time needed to execute a parallel computation using one thread, and span, the minimum amount of time needed to execute a parallel computation, for any amount of threads. Given a tree on n nodes stored as a sequence of balanced parentheses, our first algorithm builds a succinct tree representation with O(n) work, O(lgn) span and supports a rich set of operations in O(lgn) time. Our second algorithm improves the query support. It constructs a succinct representation that supports queries in O(c) time, taking O(n+nlgcnlg(nlgcn)+cc) work and O(c+lg(ncclgcn)) span, for any positive constant c. Both algorithms use O(nlgn) bits of working space. In experiments using up to 64 cores on inputs of different sizes, our first algorithm achieved good parallel speed-up. We also present an algorithm that takes O(n) work and O(lgn) span to construct the balanced parenthesis sequence of the input tree required by our succinct tree construction algorithm.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We show that any embedding of a planar graph can be encoded succinctly while efficiently answering a number of topological queries near-optimally. More precisely, we build on a succinct ...representation that encodes an embedding of m edges within 4m bits, which is close to the information-theoretic lower bound of about 3.58m. With 4m+o(m) bits of space, we show how to answer a number of topological queries relating nodes, edges, and faces, most of them in any time in ω(1). Indeed, 3.58m+o(m) bits suffice if the graph has no self-loops and no nodes of degree one. Further, we show that with O(m) bits of space we can solve all those operations in O(1) time.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We propose new succinct representations of ordinal trees and match various space/time lower bounds. It is known that any
n
-node static tree can be represented in 2
n
+
o
(
n
) bits so that a number ...of operations on the tree can be supported in constant time under the word-RAM model. However, the data structures are complicated and difficult to dynamize. We propose a simple and flexible data structure, called the
range min-max tree
, that reduces the large number of relevant tree operations considered in the literature to a few primitives that are carried out in constant time on polylog-sized trees. The result is extended to trees of arbitrary size, retaining constant time and reaching 2
n
+
O
(
n
/polylog(
n
)) bits of space. This space is optimal for a core subset of the operations supported and significantly lower than in any previous proposal.
For the dynamic case, where insertion/deletion (indels) of nodes is allowed, the existing data structures support a very limited set of operations. Our data structure builds on the range min-max tree to achieve 2
n
+
O
(
n
/log
n
) bits of space and
O
(log
n
) time for all operations supported in the static scenario, plus indels. We also propose an improved data structure using 2
n
+
O
(
n
log log
n
/log
n
) bits and improving the time to the optimal
O
(log
n
/log log
n
) for most operations. We extend our support to forests, where whole subtrees can be attached to or detached from others, in time
O
(log
1+ϵ
n
) for any ϵ > 0. Such operations had not been considered before.
Our techniques are of independent interest. An immediate derivation yields an improved solution to range minimum/maximum queries where consecutive elements differ by ± 1, achieving
n
+
O
(
n
/polylog(
n
)) bits of space. A second one stores an array of numbers supporting operations
sum
and
search
and limited updates, in optimal time
O
(log
n
/log log
n
). A third one allows representing dynamic bitmaps and sequences over alphabets of size σ, supporting rank/select and indels, within zero-order entropy bounds and time
O
(log
n
log σ/(log log
n
)
2
) for all operations. This time is the optimal
O
(log
n
/log log
n
) on bitmaps and polylog-sized alphabets. This improves upon the best existing bounds for entropy-bounded storage of dynamic sequences, compressed full-text self-indexes, and compressed-space construction of the Burrows-Wheeler transform.
We consider the problem of designing succinct navigational oracles, i.e., succinct data structures supporting basic navigational queries such as degree, adjacency and neighborhood efficiently for ...intersection graphs on a circle, which include graph classes such as circle graphs, k-polygon-circle graphs, circle-trapezoid graphs, trapezoid graphs. The degree query reports the number of incident edges to a given vertex, the adjacency query asks if there is an edge between two given vertices, and the neighborhood query enumerates all the neighbors of a given vertex. We first prove a general lower bound for these intersection graph classes, and then present a uniform approach that lets us obtain matching lower and upper bounds for representing each of these graph classes. More specifically, our lower bound proofs use a unified technique to produce tight bounds for all these classes, and this is followed by our data structures which are also obtained from a unified representation method to achieve succinctness for each class. In addition, we prove a lower bound of space for representing trapezoid graphs, and give a succinct navigational oracle for this class of graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We introduce LZ-End, a new member of the Lempel–Ziv family of text compressors, which achieves compression ratios close to those of LZ77 but is much faster at extracting arbitrary text substrings. We ...then build the first self-index based on LZ77 (or LZ-End) compression, which in addition to text extraction offers fast indexed searches on the compressed text. This self-index is particularly effective for representing highly repetitive sequence collections, which arise for example when storing versioned documents, software repositories, periodic publications, and biological sequence databases.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
We present a zero-knowledge argument for NP with low communication complexity, low concrete cost for both the prover and the verifier, and no trusted setup, based on standard cryptographic ...assumptions. Communication is proportional to d log G (for d the depth and G the width of the verifying circuit) plus the square root of the witness size. When applied to batched or data-parallel statements, the prover's runtime is linear and the verifier's is sub-linear in the verifying circuit size, both with good constants. In addition, witness-related communication can be reduced, at the cost of increased verifier runtime, by leveraging a new commitment scheme for multilinear polynomials, which may be of independent interest. These properties represent a new point in the tradeoffs among setup, complexity assumptions, proof size, and computational cost. We apply the Fiat-Shamir heuristic to this argument to produce a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) in the random oracle model, based on the discrete log assumption, which we call Hyrax. We implement Hyrax and evaluate it against five state-of-the-art baseline systems. Our evaluation shows that, even for modest problem sizes, Hyrax gives smaller proofs than all but the most computationally costly baseline, and that its prover and verifier are each faster than three of the five baselines.
PDF
