Search

Let C and D be hereditary graph classes. Consider the following problem: given a graph G ∈ D , find a largest, in terms of the number of vertices, induced subgraph of G that belongs to C . We prove that it can be solved in 2 o (n) time, where n is the number of vertices of G, if the following conditions are satisfied: the graphs in C are sparse, i.e., they have linearly many edges in terms of the number of vertices; the graphs in D admit balanced separators of size governed by their density, e.g., O (Δ) or O (m) , where Δ and m denote the maximum degree and the number of edges, respectively; and the considered problem admits a single-exponential fixed-parameter algorithm when parameterized by the treewidth of the input graph. This leads, for example, to the following corollaries for specific classes C and D : a largest induced forest in a P t -free graph can be found in 2 O ~ (n 2 / 3) time, for every fixed t; and a largest induced planar graph in a string graph can be found in 2 O ~ (n 2 / 3) time. [ABSTRACT FROM AUTHOR]

We consider subexponential algorithms finding weighted homomorphisms from intersection graphs of curves (string graphs) with n vertices to a fixed graph H. We provide a complete dichotomy: if H has no two vertices sharing two common neighbors, then the problem can be solved in time 2 O (n 2 / 3 log ⁡ n) , otherwise there is no subexponential algorithm, assuming the ETH. Then we consider locally constrained homomorphisms. We show that for each target graph H , the locally injective and locally bijective homomorphism problems can be solved in time 2 O (n log ⁡ n) in string graphs. For locally surjective homomorphisms we show a dichotomy for H being a path or a cycle. If H is P 3 or C 4 , then the problem can be solved in time 2 O (n 2 / 3 log 3 / 2 ⁡ n) in string graphs; otherwise, assuming the ETH, there is no subexponential algorithm. As corollaries, we obtain new results concerning the complexity of homomorphism problems in P t -free graphs. [ABSTRACT FROM AUTHOR]

Background: De novo genome assembly relies on two kinds of graphs: de Bruijn graphs and overlap graphs. Overlap graphs are the basis for the Celera assembler, while de Bruijn graphs have become the dominant technical device in the last decade. Those two kinds of graphs are collectively called assembly graphs. Results: In this review, we discuss the most recent advances in the problem of constructing, representing and navigating assembly graphs, focusing on very large datasets. We will also explore some computational techniques, such as the Bloom filter, to compactly store graphs while keeping all functionalities intact. Conclusions: We complete our analysis with a discussion on the algorithmic issues of assembling from long reads (e.g., PacBio and Oxford Nanopore). Finally, we present some of the most relevant open problems in this field. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Abstract: We investigate the class of vertex intersection graphs of paths on a grid, and specifically consider the subclasses that are obtained when each path in the representation has at most k bends (turns). We call such a subclass the -VPG graphs, . We present a complete hierarchy of VPG graphs relating them to other known families of graphs. String graphs are equivalent to VPG graphs. The grid intersection graphs [S. Bellantoni, I. Ben-Arroyo Hartman, T. Przytycka, S. Whitesides, Grid intersection graphs and boxicity, Discrete Math. 114, (1993), 41–49; I. Ben-Arroyo Hartman, I. Newman, R. Ziv, On grid intersection graphs, Discrete Math. 87(1), (1991), 41–52] are shown to be equivalent to the bipartite -VPG graphs. Chordal -VPG graphs are shown to be exactly Strongly Chordal -VPG graphs. We prove the strict containment of -VPG and circle graphs into -VPG. Planar graphs are known to be in the class of string graphs, and we prove here that planar graphs are -VPG graphs. In the case of -VPG graphs, we observe that a set of horizontal and vertical segments have strong Helly number 2. We show that the coloring problem for -VPG graphs, for , is NP-complete and give a 2-approximation algorithm for coloring -VPG graphs. Furthermore, we prove that triangle-free -VPG graphs are 4-colorable, and this is best possible. [Copyright &y& Elsevier]