Search

It is known that every graph of sufficiently large chromatic number and bounded clique number contains, as an induced subgraph , a subdivision of any fixed forest, and a subdivision of any fixed cycle. Equivalently, every forest is pervasive, and K 3 is pervasive, in the class of all graphs, where we say a graph H is “pervasive” (in some class of graphs) if for all l ≥ 1 , every graph in the class of bounded clique number and sufficiently large chromatic number has an induced subgraph that is a subdivision of H, in which every edge of H is replaced by a path of at least l edges. Which other graphs are pervasive? It was proved by Chalopin, Esperet, Li and Ossona de Mendez that every such graph is a “forest of lanterns”: roughly, every block is a “lantern”, a graph obtained from a tree by adding one extra vertex, and there are rules about how the blocks fit together. It is not known whether every forest of lanterns is pervasive in the class of all graphs; but in another paper two of us prove that all “banana trees” are pervasive, that is, multigraphs obtained from a forest by adding parallel edges, thus generalizing the two results above. This paper contains the first half of the proof, which works for any forest of lanterns, not just for banana trees. Say a class of graphs is “ρ-controlled” if for every graph in the class, its chromatic number is at most some function (determined by the class) of the largest chromatic number of a ρ-ball in the graph. In this paper we prove that for every ρ ≥ 2 , and for every ρ-controlled class, every forest of lanterns is pervasive in this class. These results turn out particularly nicely when applied to string graphs. A “chandelier” is a special lantern, a graph obtained from a tree by adding a vertex adjacent to precisely the leaves of the tree. A “string graph” is the intersection graph of a set of curves in the plane. There are string graphs with clique number two and chromatic number arbitrarily large. We prove that the class of string graphs is 2-controlled, and consequently every forest of lanterns is pervasive in this class; but in fact something stronger is true, that every string graph of sufficiently large chromatic number and bounded clique number contains each fixed chandelier as an induced subgraph (not just as a subdivision); and the same for most forests of chandeliers (there is an extra condition on how the blocks are attached together).

A string graph is the intersection graph of curves in the plane. We prove that for every e>0, if G is a string graph with n vertices such that the edge density of G is below 1/4−e, then V(G) contains two linear sized subsets A and B with no edges between them. The constant 1/4 is a sharp threshold for this phenomenon as there are string graphs with edge density less than 1/4+e such that there is an edge connecting any two logarithmic sized subsets of the vertices. The existence of linear sized sets A and B with no edges between them in sufficiently sparse string graphs is a direct consequence of a recent result of Lee about separators. Our main theorem finds the largest possible density for which this still holds. In the special case when the curves are x-monotone, the same result was proved by Pach and the author of this paper, who also proposed the conjecture for the general case., Discrete & Computational Geometry, 67 (1), ISSN:0179-5376, ISSN:1432-0444

A string graph is the intersection graph of a family of continuous arcs in the plane. The intersection graph of a family of plane convex sets is a string graph, but not all string graphs can be obtained in this way. We prove the following structure theorem conjectured by Janson and Uzzell: The vertex set of almost all string graphs on n vertices can be partitioned into five cliques such that some pair of them is not connected by any edge ($$n\rightarrow \infty $$). We also show that every graph with the above property is an intersection graph of plane convex sets. As a corollary, we obtain that almost all string graphs on n vertices are intersection graphs of plane convex sets.

Background De novo genome assembly is a technique that builds the genome of a specimen using overlaps of genomic fragments without additional work with reference sequence. Sequence fragments (called reads) are assembled as contigs and scaffolds by the overlaps. The quality of the de novo assembly depends on the length and continuity of the assembly. To enable faster and more accurate assembly of species, existing sequencing techniques have been proposed, for example, high-throughput next-generation sequencing and long-reads-producing third-generation sequencing. However, these techniques require a large amounts of computer memory when very huge-size overlap graphs are resolved. Also, it is challenging for parallel computation. Results To address the limitations, we propose an innovative algorithmic approach, called Scalable Overlap-graph Reduction Algorithms (SORA). SORA is an algorithm package that performs string graph reduction algorithms by Apache Spark. The SORA’s implementations are designed to execute de novo genome assembly on either a single machine or a distributed computing platform. SORA efficiently compacts the number of edges on enormous graphing paths by adapting scalable features of graph processing libraries provided by Apache Spark, GraphX and GraphFrames. Conclusions We shared the algorithms and the experimental results at our project website, https://github.com/BioHPC/SORA. We evaluated SORA with the human genome samples. First, it processed a nearly one billion edge graph on a distributed cloud cluster. Second, it processed mid-to-small size graphs on a single workstation within a short time frame. Overall, SORA achieved the linear-scaling simulations for the increased computing instances.

Noncoding RNAs (ncRNAs) play important regulatory and functional roles in microorganisms, such as regulation of gene expression, signaling, protein synthesis, and RNA processing. Hence, their classification and quantification are central tasks toward the understanding of the function of the microbial community. However, the majority of the current metagenomic sequencing technologies generate short reads, which may contain only a partial secondary structure that complicates ncRNA homology detection. Meanwhile, de novo assembly of the metagenomic sequencing data remains challenging for complex communities. To tackle these challenges, we developed a novel algorithm called DRAGoM (Detection of RNA using Assembly Graph from Metagenomic data). DRAGoM first constructs a hybrid graph by merging an assembly string graph and an assembly de Bruijn graph. Then, it classifies paths in the hybrid graph and their constituent readsinto differentncRNA families based on both sequence and structural homology. Our benchmark experiments show that DRAGoMcan improve the performance and robustness over traditional approaches on the classification and quantification of a wide class of ncRNA families.

Although most existing genome assemblers are based on the de Bruijn graphs, it remains unclear how to construct these graphs for large genomes and largek-mer sizes. This algorithmic challenge has become particularly important with the emergence of long high-fidelity (HiFi) reads that were recently utilized to generate a semi-manual telomere-to-telomere assembly of the human genome and to get a glimpse into biomedically important regions that evaded all previous attempts to sequence them. To enable automated assemblies of long and accurate reads, we developed a fast LJA algorithm that reduces the error rate in these reads by three orders of magnitude (making them nearly error-free) and constructs the de Bruijn graph for large genomes and largek-mer sizes. Since the de Bruijn graph constructed for a fixedk-mer size is typically either too tangled or too fragmented, LJA uses a new concept of a multiplex de Bruijn graph with varyingk-mer sizes. We demonstrate that LJA improves on the state-of-the-art assemblers with respect to both accuracy and contiguity and enables automated telomere-to-telomere assemblies of entire human chromosomes.

Background Next-generation sequencing technologies revolutionized genomics by producing high-throughput reads at low cost, and this progress has prompted the recent development of de novo assemblers. Multiple assembly methods based on de Bruijn graph have been shown to be efficient for Illumina reads. However, the sequencing errors generated by the sequencer complicate analysis of de novo assembly and influence the quality of downstream genomic researches. Results In this paper, we develop a de Bruijn assembler, called Clover (clustering-oriented de novo assembler), that utilizes a novel k-mer clustering approach from the overlap-layout-consensus concept to deal with the sequencing errors generated by the Illumina platform. We further evaluate Clover’s performance against several de Bruijn graph assemblers (ABySS, SOAPdenovo, SPAdes and Velvet), overlap-layout-consensus assemblers (Bambus2, CABOG and MSR-CA) and string graph assembler (SGA) on three datasets (Staphylococcus aureus, Rhodobacter sphaeroides and human chromosome 14). The results show that Clover achieves a superior assembly quality in terms of corrected N50 and E-size while remaining a significantly competitive in run time except SOAPdenovo. In addition, Clover was involved in the sequencing projects of bacterial genomes Acinetobacter baumannii TYTH-1 and Morganella morganii KT. Conclusions The marvel clustering-based approach of Clover that integrates the flexibility of the overlap-layout-consensus approach and the efficiency of the de Bruijn graph method has high potential on de novo assembly. Now, Clover is freely available as open source software from https://oz.nthu.edu.tw/~d9562563/src.html.

One of the most computationally intensive tasks in computational biology is de novo genome assembly, the decoding of the sequence of an unknown genome from redundant and erroneous short sequences. A common assembly paradigm identifies overlapping sequences, simplifies their layout, and creates consensus. Despite many algorithms developed in the literature, the efficient assembly of large genomes is still an open problem. In this work, we introduce new distributed-memory parallel algorithms for overlap detection and layout simplification steps of de novo genome assembly, and implement them in the diBELLA 2D pipeline. Our distributed memory algorithms for both overlap detection and layout simplification are based on linear-algebra operations over semirings using 2D distributed sparse matrices. Our layout step consists of performing a transitive reduction from the overlap graph to a string graph. We provide a detailed communication analysis of the main stages of our new algorithms. diBELLA 2D achieves near linear scaling with over 80% parallel efficiency for the human genome, reducing the runtime for overlap detection by 1.2 – $1.3 \times$ for the human genome and 1.5 – $1.9 \times$ for C.elegans compared to the state-of-the-art. Our transitive reduction algorithm outperforms an existing distributed-memory implementation by 10.5 – $13.3 \times$ for the human genome and 18– $29 \times$ for the C. elegans. Our work paves the way for efficient de novo assembly of large genomes using long reads in distributed memory.

Correspondence problems are challenging due to the complexity of real-world scenes. One way to solve this problem is to improve the graph matching (GM) process, which is flexible for matching non-rigid objects. GM can be classified into three categories that correspond with the variety of object functions: first-order, second-order, and high-order matching. Graph and hypergraph matching have been proposed separately in previous works. The former is equivalent to the second-order GM, and the latter is equivalent to high-order GM, but we use the terms second- and high-order GM to unify the terminology in this paper. Second- and high-order GM fit well with different types of problems; the key goal for these processes is to find better-optimized algorithms. Because the optimal problems for second- and high-order GM are different, we propose two novel optimized algorithms for them in this paper. (1) For the second-order GM, we first introduce a $K$ -nearest-neighbor-pooling matching method that integrates feature pooling into GM and reduces the complexity. Meanwhile, we evaluate each matching candidate using discriminative weights on its $k$ -nearest neighbors by taking locality as well as sparsity into consideration. (2) High-order GM introduces numerous outliers, because precision is rarely considered in related methods. Therefore, we propose a sub-pattern structure to construct a robust high-order GM method that better integrates geometric information. To narrow the search space and solve the optimization problem, a new prior strategy and a cell-algorithm-based Markov Chain Monte Carlo framework are proposed. In addition, experiments demonstrate the robustness and improvements of these algorithms with respect to matching accuracy compared with other state-of-the-art algorithms.

We examine the conditions under which a signed graph contains an edge or a vertex that is contained in a unique negative circle or a unique positive circle. For an edge in a unique signed circle, the positive and negative case require the same structure on the underlying graph, but the requirements on the signature are different. We characterize the structure of the underlying graph necessary to support such an edge in terms of bridges of a circle. We then use the results from the edge version of the problem to help solve the vertex version., Comment: 12 pages, 4 figures

Deadlock prevention techniques are essential in the design of robust distributed systems. However, despite the large number of different algorithmic approaches to detect and solve deadlock situations, yet there remains quite a wide field to be explored in the study of deadlock-related combinatorial properties. In this work we consider a simplified AND-OR model, where the processes and their communication are given as a graph G. Each vertex of G is labelled AND or OR, in such a way that an AND-vertex (resp., OR-vertex) depends on the computation of all (resp., at least one) of its neighbors. We define a graph convexity based on this model, such that a set $$S \subseteq V(G)$$ is convex if and only if every AND-vertex (resp., OR-vertex) $$v \in V(G){\setminus }S$$ has at least one (resp., all) of its neighbors in $$V(G) {\setminus } S$$ . We relate some classical convexity parameters to blocking sets that cause deadlock. In particular, we show that those parameters in a graph represent the sizes of minimum or maximum blocking sets, and also the computation time until system stability is reached. Finally, a study on the complexity of combinatorial problems related to such graph convexity is provided.

The ever increasing size of graphs makes them difficult to query and store. In this paper, we present Shrink, a compression method that reduces the size of the graph while preserving the distances between the nodes. The compression is based on the iterative merging of the nodes. During each merging, a system of linear equations is solved to define new edge weights in a way that the new weights have the least effect on the distances. Merging nodes continues until the desired size for the compressed graph is reached. The compressed graph, also known as the coarse graph, can be queried without decompression. As the complexity of distance-based queries such as shortest path queries is highly dependent on the size of the graph, Shrink improves the performance in terms of time and storage. Shrink not only provides the length of the shortest path but also identifies the nodes on the path. The approach has been applied to both weighted and unweighted graphs including road network, friendship network, collaboration network, web graph and social network. In the experiment, a road network with more than 2.5 million nodes is reduced to fifth while the average relative error is less than 1%.

Extensive use of three dimensional models in various areas indicates the importance of 3D data retrieval accuracy. In this paper, a directional graph, is introduced for 3D model retrieval. The proposed directional graph is isometric invariant and extracts the features of 3D model vertices in a way that both provides a sample of the features of each salient part and illustrates how various parts are linked and connected with each other. Directionality of the graph does not refer to a certain physical direction, but it shows the arrangement of different points in the graph. The proposed method commences with determining the salient points and continues with constructing a directional graph. Each branch of the graph starts from one salient point in the 3D model and ends in another salient point of that model. The points between the beginning and end of each branch are the vertices of 3D model from which the shortest geodesic path between these two salient points crosses. The whole graph of each model is constructed out of the accumulation of multiple branches, each of which is associated with a pair of salient points. After constructing of the directional graph, WKS is calculated in the path of graph points as the geometric feature of the model. In fact, the points of the directional graph do not provide any information on the object features and they only specify the location where the features should be calculated. The features are calculated and placed in the graph points so, the final graph is built. After completing the feature extraction process, the difference between various models is estimated using Munkres Assignment problem. The experimental results indicate the effectiveness of the directional graph in object description for non-rigid 3D model retrieval. Comparing the proposed method with other approaches by computing the evaluation parameters as well as investigating the computational complexity substantiates the superior performance of it.

Let R be a ring with identity and M be a unitary left R-module. The intersection graph of submodules of M, denoted by G(M), is defined to be a graph whose vertices are in one to one correspondence with all non-trivial submodules of M and two distinct vertices are adjacent if and only if the corresponding submodules of M have non-zero intersection. In this paper, we consider the intersection graph of submodules of a module. We determine the structure of modules whose clique numbers are finite. We show that if 1 < ω(G(M)) < ∞, then M is a direct sum of a finite module and a cyclic module, where ω(G(M)) denotes the clique number of G(M). We prove that if ω(G(M)) is not finite, then M contains an infinite clique. Among other results, it is shown that a Noetherian R-module whose intersection of all non-trivial submodules is non-zero, is Artinian.

We study a simple transportation problem on a string graph. The objective is to regulate the node levels of some decaying quantity to optimize dynamical performance. This can be achieved by controlling the flows, which are subject to delay, between neighbouring nodes. The problem is considered from two perspectives. In the first (the social perspective), all nodes cooperate to find the flows that maximize the aggregated utility of the entire transportation network. In the second (the user perspective), the nodes instead try to maximimize their own utility. Our main contribution is to give an implementation of the feedback law that gives the social optimum, that only depends on the local states and a set of prices defined by a distributed update rule. These prices align the social and user optimum in a budget neutral way, and give all nodes no worse cost than if they were on their own.

In contrast to genome assemblers that use de Bruijn graphs, those based on string graphs are able to losslessly retain information from sequence data. However, despite the advantages provided by a string graph framework in repeat detection and in maintaining read coherence, the high computational cost for constructing a string graph hinders its usability for genome assembly. Even though different algorithms have been proposed over the last decade for string graph construction, efficiency is still a challenge due to the demand for processing a large amount of sequence data generated by Next-Generation Sequencing technologies. In this paper, we provide a novel, linear time and alphabet-size-independent algorithm SOF which uses the property of irreducible edges and transitive edges to efficiently construct a string graph from an overlap graph. Experimental results show that SOF is at least 2.3 times faster than the string graph construction algorithm provided in SGA (one of the most popular string graph-based assemblers), while maintaining almost the same memory footprint as SGA. Moreover, the implementation of SOF as a subprogram in the SGA assembly pipeline will allow a user easy access to the preprocessing and postprocessing steps for genome assembly provided in SGA. Implementation: https://github.com/iqbalmorshed/sof

Aligning DNA sequences to an annotated reference is a key step for genotyping in biology. Recent scientific studies have demonstrated improved inference by aligning reads to a variation graph, i.e., a reference sequence augmented with known genetic variations. Given a variation graph in the form of a directed acyclic string graph, the sequence to graph alignment problem seeks to find the best matching path in the graph for an input query sequence. Solving this problem exactly using a sequential dynamic programming algorithm takes quadratic time in terms of the graph size and query length, making it difficult to scale to high throughput DNA sequencing data. In this work, we propose the first parallel algorithm for computing sequence to graph alignments that leverages multiple cores and single-instruction multiple-data (SIMD) operations. We take advantage of the available inter-task parallelism, and provide a novel blocked approach to compute the score matrix while ensuring high memory locality. Using a 48-core Intel Xeon Skylake processor, the proposed algorithm achieves peak performance of 317 billion cell updates per second (GCUPS), and demonstrates near linear weak and strong scaling on up to 48 cores. It delivers significant performance gains compared to existing algorithms, and results in run-time reduction from multiple days to three hours for the problem of optimally aligning high coverage long (PacBio/ONT) or short (Illumina) DNA reads to an MHC human variation graph containing 10 million vertices.AvailabilityThe implementation of our algorithm is available at https://github.com/ParBLiSS/PaSGAL. Data sets used for evaluation are accessible using https://alurulab.cc.gatech.edu/PaSGAL.

The de Bruijn Graph algorithm (DBG) as one of the cornerstones algorithms in short read assembly has extended with the rapid advancement of the Next Generation Sequencing (NGS) technologies and low-cost production of millions of high-quality short reads. Erroneous reads, non-uniform coverage, and genomic repeats are three major problems that influence the performance of short read assemblers. To encounter these problems, the iterative DBG algorithm applies multiple [Formula: see text]-mers instead of a single [Formula: see text]-mer, by iterating the DBG graph over a range of [Formula: see text]-mer sizes from the minimum to the maximum. However, the iteration paradigm of iterative DBG deals with complex graphs from the beginning of the algorithm and therefore, causes more potential errors and computational time for resolving various unreal branches. In this research, we propose the Reverse Modified Iterative DBG graph (named RMI-DBG) for short read assembly. RMI-DBG utilizes the DBG algorithm and String graph to achieve the advantages of both algorithms. We present that RMI-DBG performs faster with comparable results in comparison to iterative DBG. Additionally, the quality of the proposed algorithm in terms of continuity and accuracy is evaluated with some commonly-used assemblers via several real datasets of the GAGE-B benchmark.

Studying the space-like graph surfaces of codimension 2 on the five-dimensional sub-Lorentzian structures with two negative directions of distinct degrees, we determine the differential properties of graph mappings and prove the area formula for the corresponding image surfaces.

Motivation In the context of third-generation long-read sequencing technologies, read-overlap-based approaches are expected to play a central role in the assembly step. A fundamental challenge in assembling from a read-overlap graph is that the true sequence corresponds to a Hamiltonian path on the graph, and, under most formulations, the assembly problem becomes NP-hard, restricting practical approaches to heuristics. In this work, we avoid this seemingly fundamental barrier by first setting the computational complexity issue aside, and seeking an algorithm that targets information limits. In particular, we consider a basic feasibility question: when does the set of reads contain enough information to allow unambiguous reconstruction of the true sequence? Results Based on insights from this information feasibility question, we present an algorithm—the Not-So-Greedy algorithm—to construct a sparse read-overlap graph. Unlike most other assembly algorithms, Not-So-Greedy comes with a performance guarantee: whenever information feasibility conditions are satisfied, the algorithm reduces the assembly problem to an Eulerian path problem on the resulting graph, and can thus be solved in linear time. In practice, this theoretical guarantee translates into assemblies of higher quality. Evaluations on both simulated reads from real genomes and a PacBio Escherichia coli K12 dataset demonstrate that Not-So-Greedy compares favorably with standard string graph approaches in terms of accuracy of the resulting read-overlap graph and contig N50. Availability Available at github.com/samhykim/nsg Contact courtade@eecs.berkeley.edu or dntse@stanford.edu Supplementary information Supplementary data are available at Bioinformatics online.

DNA sequence assembly is a rich combinatorial problem that arose with the first DNA sequencing projects in the early 80's. Here we give a short history of the progression of algorithmic ideas used to solve the de novo problem of inferring a genome given a large sampling of substrings covering it. This classic inverse problem is compounded by a variety of experimental features and artifacts that must be considered in any realistic solution. While current methods produce very good results, the perfect assembler has yet to be built.

Some recent results (Bauer et al. in Algorithms in bioinformatics, Springer, Berlin, pp 326---337, 2012; Cox et al. in Algorithms in bioinformatics, Springer, Berlin, pp. 214---224, 2012; Rosone and Sciortino in The nature of computation. Logic, algorithms, applications, Springer, Berlin, pp 353---364, 2013) have introduced external-memory algorithms to compute self-indexes of a set of strings, mainly via computing the Burrows---Wheeler transform of the input strings. The motivations for those results stem from Bioinformatics, where a large number of short strings (called reads) are routinely produced and analyzed. In that field, a fundamental problem is to assemble a genome from a large set of much shorter samples extracted from the unknown genome. The approaches that are currently used to tackle this problem are memory-intensive. This fact does not bode well with the ongoing increase in the availability of genomic data. A data structure that is used in genome assembly is the string graph, where vertices correspond to samples and arcs represent two overlapping samples. In this paper we address an open problem of Simpson and Durbin (Bioinformatics 26(12):i367---i373, 2010): to design an external-memory algorithm to compute the string graph.

Let $G$ be a graph and let $I := I (G)$ be its edge ideal. In this paper, we provide an upper bound of $n$ from which $\depth R/ I(G)^n$ is stationary, and compute this limit explicitly. This bound is always achieved if $G$ has no cycles of length $4$ and every its connected component is either a tree or a unicyclic graph., Comment: To appear in Journal of Algebra

A graph G is called (k,d)∗-choosable if for every list assignment L satisfying ∣L(v)∣ ≥k for all v∈V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this paper, it is proved that every graph of nonnegative characteristic without intersecting i-cycles for all i=3,4,5 is (3,1)∗-choosable.

We study limits of convergent sequences of string graphs, that is graphs with an intersection representation consisting of curves in the plane. We use these results to study the limiting behavior of a sequence of random string graphs. We also prove similar results for several related graph classes.

Finding the overlaps between sequences that are generated by Next Generation Sequencing (NGS) technology is a time- and space-consuming step in building a string graph in genome assembly. The problem is known in computer science as all-pairs suffix prefix (APSP). The problem has been tackled since 1992 and several solutions were presented to solve it. While some of them achieve optimal theoretical time consumption, they have a very high space-consumption in addition to being practically slow due to a raised constant factor. Some other recent solutions practically consume much less space and time to solve APSP despite their adaptations to techniques and data structures which don’t have optimal worst-case asymptotic complexity. Other few researches tackled the approximate version of the overlap problem hoping to avoid error-detecting stages in genome assembly. These solutions used the same data structures which were employed to solve APSP in addition to some advanced techniques in order to address the complexity of approximate matching. In this work, we evaluate these recent algorithms, in terms of time and space, in both exact and approximate formats. Our results show that FastAPSP has the best time-consumption unless the size of the data set is large. The high space demand of such large data sets would favor the usage of SOF and Readjoiner. Our experiments also show that AOF is, in general, faster than FM unless the data set is small and repetitive. In addition, it can handle large data sets that cannot be processed by FM.

Given a family of curves \(\mathcal {C}\) in the plane, its disjointness graph is the graph whose vertices correspond to the elements of \(\mathcal {C}\), and two vertices are joined by an edge if and only if the corresponding sets are disjoint. We prove that for every positive integer r and n, there exists a family of n curves whose disjointness graph has girth r and chromatic number \(\varOmega (\frac{1}{r}\log n)\). In the process we slightly improve Bollobas’s old result on Hasse diagrams and show that our improved bound is best possible for uniquely generated partial orders.

A string graph is an intersection graph of simple curves on the plane. For \(k\ge 0\), \(B_k\)-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends). It is well-known that any string graph is a \(B_k\)-VPG graph for some value of k. For \(k\ge 0\), unit \(B_k\)-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. Any string graph is a unit-\(B_k\)-VPG graph for some value of k.

The advent of high-throughput DNA sequencing techniques has permitted very high quality de novo assemblies of genomes, but raise an issue of requiring large amounts of computer memory to resolve the large genome graphs generated by most overlap graph de novo assemblers. To address these limitations, we present a novel algorithmic approach; Scalable Overlap-graph Reduction Algorithms (SORA). SORA adapts string graph reduction algorithms for the genome assembly using a distributed computing platform. To efficiently compute coverage for enormous paths in the graphs, SORA uses Apache Spark which is a cluster-based engine designed on top of Hadoop to handle very large datasets in the cloud. The experimental results show that SORA can process a nearly one billion edge graph in a distributed cloud cluster as well as smaller graphs on a local cluster with a short turnaround time. Moreover, our algorithms scale almost linearly with increasing numbers of virtual instances in the cloud. SORA is freely available for download at https://github.com/BioHPC/SORA/.

Summary: De novo genome assembly is an important application on both uncharacterized genome assembly and variant identification in a reference-unbiased way. In comparison with de Brujin graph, string graph is a lossless data representation for de novo assembly. However, string graph construction is computational intensive. We propose GraphSeq to accelerate string graph construction by leveraging the distributed computing framework.Availability and Implementation: GraphSeq is implemented with Scala on Spark and freely available at https://www.atgenomix.com/blog/graphseq.Supplementary information: Supplementary data are available at Bioinformatics online.

MotivationThe de Bruijn graph is a simple and efficient data structure that is used in many areas of sequence analysis including genome assembly, read error correction and variant calling. The data structure has a single parameter k, is straightforward to implement and is tractable for large genomes with high sequencing depth. It also enables representation of multiple samples simultaneously to facilitate comparison. However, unlike the string graph, a de Bruijn graph does not retain long range information that is inherent in the read data. For this reason, applications that rely on de Bruijn graphs can produce sub-optimal results given their input.ResultsWe present a novel assembly graph data structure: the Linked de Bruijn Graph (LdBG). Constructed by adding annotations on top of a de Bruijn graph, it stores long range connectivity information through the graph. We show that with error-free data it is possible to losslessly store and recover sequence from a Linked de Bruijn graph. With assembly simulations we demonstrate that the LdBG data structure outperforms both the de Bruijn graph and the String Graph Assembler (SGA). Finally we apply the LdBG to Klebsiella pneumoniae short read data to make large (12 kbp) variant calls, which we validate using PacBio sequencing data, and to characterise the genomic context of drug-resistance genes.AvailabilityLinked de Bruijn Graphs and associated algorithms are implemented as part of McCortex, available under the MIT license at https://github.com/mcvean/mccortex.Contactturner.isaac@gmail.com.

Let G = (V;E) be a connected graph. A subset S of V (G) is called a boundary dominating set if every vertex of V S is boundary dominated by some vertex of S. The minimum taken over all boundary dominating sets of a graphG is called the boundary domination number ofG and is denoted by b(G). We define the boundary domatic number in graphs. Exact values of of Wheel Graph Families are obtained and some other interesting results are established.