Search

For every n, we construct two arcs in the plane that intersect at least n times and do not form spirals. The construction is in three stages: we first exhibit two closed curves on the torus that do not form double spirals, then two arcs on the torus that do not form spirals, and finally two arcs in the plane that do not form spirals. The planar arcs provide a counterexample to a proof of Pach and Tóth concerning string graphs. [ABSTRACT FROM AUTHOR]

A string graph is the intersection graph of curves in the plane. We prove that for every ϵ > 0 , if G is a string graph with n vertices such that the edge density of G is below 1 / 4 - ϵ , 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 + ϵ 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. [ABSTRACT FROM AUTHOR]

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

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 k -mers instead of a single k -mer, by iterating the DBG graph over a range of k -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. [ABSTRACT FROM AUTHOR]

Current variant discovery approaches often rely on an initial read mapping to the reference sequence. Their effectiveness is limited by the presence of gaps, potential misassemblies, regions of duplicates with a high-sequence similarity and regions of high-sequence divergence in the reference. Also, mapping-based approaches are less sensitive to large INDELs and complex variations and provide little phase information in personal genomes. A few de novo assemblers have been developed to identify variants through direct variant calling from the assembly graph, micro-assembly and whole-genome assembly, but mainly for whole-genome sequencing (WGS) data. We developed SGVar, a de novo assembly workflow for haplotype-based variant discovery from whole-exome sequencing (WES) data. Using simulated human exome data, we compared SGVar with five variation-aware de novo assemblers and with BWA-MEM together with three haplotype- or local de novo assembly-based callers. SGVar outperforms the other assemblers in sensitivity and tolerance of sequencing errors. We recapitulated the findings on whole-genome and exome data from a Utah residents with Northern and Western European ancestry (CEU) trio, showing that SGVar had high sensitivity both in the highly divergent human leukocyte antigen (HLA) region and in non-HLA regions of chromosome 6. In particular, SGVar is robust to sequencing error, k-mer selection, divergence level and coverage depth. Unlike mapping-based approaches, SGVar is capable of resolving long-range phase and identifying large INDELs from WES, more prominently from WGS. We conclude that SGVar represents an ideal platform for WES-based variant discovery in highly divergent regions and across the whole genome. [ABSTRACT FROM AUTHOR]

The string graph for a collection of next-generation reads is a lossless data representation that is fundamental for de novo assemblers based on the overlap-layout-consensus paradigm. In this article, we explore a novel approach to compute the string graph, based on the FM-index and Burrows and Wheeler Transform. We describe a simple algorithm that uses only the FM-index representation of the collection of reads to construct the string graph, without accessing the input reads. Our algorithm has been integrated into the string graph assembler (SGA) as a standalone module to construct the string graph. The new integrated assembler has been assessed on a standard benchmark, showing that fast string graph (FSG) is significantly faster than SGA while maintaining a moderate use of main memory, and showing practical advantages in running FSG on multiple threads. Moreover, we have studied the effect of coverage rates on the running times. [ABSTRACT FROM AUTHOR]

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

We provide constant factor approximation algorithms for the Minimum Dominating Set (MDS) problem on several subclasses of string graphs i.e. intersection graphs of simple curves on the plane. For k ≥ 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. We give an 18-approximation algorithm for the MDS problem on unit B 0 -VPG graphs. This partially addresses a question of Katz et al. (2005) [24]. We also give an O (k 4) -approximation algorithm for the MDS problem on unit B k -VPG graphs. We show that there is an 8-approximation algorithm for the MDS problem on vertically-stabbed L -graphs. We also give a 656-approximation algorithm for the MDS problem on stabbed rectangle overlap graphs. This is the first constant-factor approximation algorithm for the MDS problem on stabbed rectangle overlap graphs and extends a result of Bandyapadhyay et al. (2019) [31]. We prove some hardness results to complement the above results. [ABSTRACT FROM AUTHOR]

Abstract: Given a collection of curves in the plane, its string graph is defined as the graph with vertex set , in which two curves in are adjacent if and only if they intersect. Given a partially ordered set , its incomparability graph is the graph with vertex set , in which two elements of are adjacent if and only if they are incomparable. It is known that every incomparability graph is a string graph. For “dense” string graphs, we establish a partial converse of this statement. We prove that for every there exists with the property that if is a collection of curves whose string graph has at least edges, then one can select a subcurve of each such that the string graph of the collection has at least edges and is an incomparability graph. We also discuss applications of this result to extremal problems for string graphs and edge intersection patterns in topological graphs. [Copyright &y& Elsevier]

Solenodons are insectivores that live in Hispaniola and Cuba. They form an isolated branch in the tree of placental mammals that are highly divergent from other eulipothyplan insectivores The history, unique biology, and adaptations of these enigmatic venomous species could be illuminated by the availability of genome data. However, a whole genome assembly for solenodons has not been previously performed, partially due to the difficulty in obtaining samples from the field. Island isolation and reduced numbers have likely resulted in high homozygosity within the Hispaniolan solenodon (Solenodon paradoxus). Thus, we tested the performance of several assembly strategies on the genome of this genetically impoverished species. The string graph–based assembly strategy seemed a better choice compared to the conventional de Bruijn graph approach due to the high levels of homozygosity, which is often a hallmark of endemic or endangered species. A consensus reference genome was assembled from sequences of 5 individuals from the southern subspecies (S. p. woodi). In addition, we obtained an additional sequence from 1 sample of the northern subspecies (S. p. paradoxus). The resulting genome assemblies were compared to each other and annotated for genes, with an emphasis on venom genes, repeats, variable microsatellite loci, and other genomic variants. Phylogenetic positioning and selection signatures were inferred based on 4,416 single-copy orthologs from 10 other mammals. We estimated that solenodons diverged from other extant mammals 73.6 million years ago. Patterns of single-nucleotide polymorphism variation allowed us to infer population demography, which supported a subspecies split within the Hispaniolan solenodon at least 300 thousand years ago. [ABSTRACT FROM AUTHOR]