Abstract A graph $$G=(V,E)$$ G = ( V , E ) is a star-k-pairwise compatibility graph (star-k-PCG) if there exists a weight function $$w: V \rightarrow \mathbb {R}^+$$ w : V → R + and k mutually exclusive intervals $$I_1, I_2, \ldots I_k$$ I 1 , I 2 , … I k , such that there is an edge $$uv \in E$$ u v ∈ E if and only if $$w(u)+w(v) \in \bigcup _i I_i$$ w ( u ) + w ( v ) ∈ ⋃ i I i . These graphs are related to two important classes of graphs: pairwise compatibility graphs (PCGs) and multithreshold graphs. It is known that for any graph G there exists a k such that G is a star-k-PCG. Thus, for a given graph G it is interesting to know which is the minimum k such that G is a star-k-PCG. We define this minimum k as the star number of the graph, denoted by $$\gamma (G)$$ γ ( G ) . Here we investigate the star number of simple graph classes, such as graphs of small size, caterpillars, cycles and grids. Specifically, we determine the exact value of $$\gamma (G)$$ γ ( G ) for all the graphs with at most 7 vertices. By doing so we show that the smallest graphs with star number 2 are only 4 and have exactly 5 vertices; the smallest graphs with star number 3 are only 3 and have exactly 7 vertices. Next, we provide a construction showing that the star number of caterpillars is one. Moreover, we show that the star number of cycles and two-dimensional grid graphs is 2 and that the star number of 4-dimensional grids is at least 3. Finally, we conclude with numerous open problems.

BACKGROUND: Cophylogeny reconciliation is a powerful method for analyzing host-symbiont coevolution. The cophylogeny problem consists of mapping the phylogenetic tree of the symbionts into the one of the hosts, including events such as duplications, co-speciation, host-switches, and extinctions by comparing the discrepancies between the topologies of the associated symbiont evolutionary trees. Visualizing tree reconciliations is important for biologists as it aids in understanding and identifying specific patterns in the coevolution of hosts and symbionts. Additionally, when multiple optimal solutions exist, it allows for the quick comparison of different reconciliations between the same pair of trees. RESULTS: Here, we present VIRI (visual inspector of reconciliation instances), a new tree reconciliation visualizer. We adopt a hybrid metaphor combining space-filling (for host trees) and node-link (for symbiont trees) approaches, implementing the algorithms described in Calamoneri et al. (Theor Comput Sci 815:228-245. https://doi.org/10.1016/j.tcs.2019.12.024 , 2020). The visualizations produced by VIRI are designed to be clear and interpretable, thanks to an unambiguous, top-down layout of tree reconciliations and the preservation of the user's mental map when comparing multiple reconciliations on the same pair of trees. In particular, the consistent use of a shared host tree layout across visualizations is a novel feature that facilitates direct comparison. Moreover, VIRI proposes a crossing-free visualization whenever possible. Finally, VIRI allows users to store datasets and download their visualizations, offering a convenient way to organize and share data. An example of visualization produced by VIRI is depicted in Fig. 1. CONCLUSIONS: VIRI efficiently produces clear and easy-to-read visualizations of tree reconciliations. VIRI is free and available at https://viri.di.uniroma1.it/ .

Abstract A graph $G=(V,E)$ is defined as a star-$k$-pairwise compatibility graph (PCG) when it is possible to assign a positive real number weight $w$ to each vertex $V$, and define $k$ distinct intervals $I_{1}, I_{2}, \ldots I_{k}$, in such a way that there is an edge $uv$ in $E$ if and only if the sum of the weights of vertices $u$ and $v$ falls within the union of these intervals. The star-$k$-PCG class is connected to two significant graph categories: PCGs and multithreshold graphs. The star number of a graph $G$, is the smallest $k$ for which $G$ is a star-$k$-PCG. In this paper, we study the effects of various graph operations, such as the addition of twins, pendant vertices, universal vertices, or isolated vertices, on the star number of the graph resulting from these operations. As significant applications of our findings, we determine the star number of lobster graphs and provide an upper bound for the star number of acyclic graphs. This is particularly interesting as determining the star number is notoriously difficult and is known only for a few classes of graphs. Indeed, for acyclic graphs, the exact value of the star number is currently known only for caterpillars [1].

Abstract Listing dense subgraphs is a fundamental task with a variety of network analytics applications. A lot of research has been done focusing on $k$-cliques, i.e. complete subgraphs on $k$ nodes. However, requiring complete connectivity between the nodes of a subgraph may be too restrictive in many real applications. Hence, in this paper, we consider a natural relaxation of cliques, called $k$-diamonds and defined as cliques of size $k$ with one missing edge. We first provide a sequential algorithm that, in $O(nm^{(k-1)/2})$ time, counts and lists all the $k$-diamonds in large graphs, for any constant $k \geq 4$. A parallel extension of the sequential algorithm is then proposed and analyzed in a MapReduce-style model, achieving the same local and total space usage of the state-of-the-art algorithms for $k$-cliques. The running time is optimal on dense graphs and $O(\sqrt{m})$ larger than $k$-clique counting if the graph is sparse. Our algorithms compute induced diamonds by analyzing the structure of directed stars formed by the graph nodes and their neighbors.

When a problem has more than one solution, it is often important, depending on the underlying context, to enumerate (i.e., to list) them all. Even when the enumeration can be done in polynomial delay, that is, spending no more than polynomial time to go from one solution to the next, this can be costly as the number of solutions themselves may be huge, including sometimes exponential. Furthermore, depending on the application, many of these solutions can be considered equivalent. The problem of an efficient enumeration of the equivalence classes or of one representative per class (without generating all the solutions), although identified as a need in many areas, has been addressed only for very few specific cases. In this paper, we provide a general framework that solves this problem in polynomial delay for a wide variety of optimization problems solvable by dynamic programming algorithms, and for certain types of equivalence relations between solutions.

Background: With the fast development of next generation sequencing technologies, increasing numbers of genomes are being de novo sequenced and assembled. However, most are in fragmental and incomplete draft status, and thus it is often difficult to know the accurate genome size and repeat content. Furthermore, many genomes are highly repetitive or heterozygous, posing problems to current assemblers utilizing short reads. Therefore, it is necessary to develop efficient assembly-independent methods for accurate estimation of these genomic characteristics. Results: Here we present a framework for modeling the distribution of k-mer frequency from sequencing data and estimating the genomic characteristics such as genome size, repeat structure and heterozygous rate. By introducing novel techniques of k-mer individuals, float precision estimation, and proper treatment of sequencing error and coverage bias, the estimation accuracy of our method is significantly improved over existing methods. We also studied how the various genomic and sequencing characteristics affect the estimation accuracy using simulated sequencing data, and discussed the limitations on applying our method to real sequencing data. Conclusion: Based on this research, we show that the k-mer frequency analysis can be used as a general and assembly-independent method for estimating genomic characteristics, which can improve our understanding of a species genome, help design the sequencing strategy of genome projects, and guide the development of assembly algorithms. The programs developed in this research are written using C/C++, and freely accessible at Github URL (https://github.com/fanagislab/GCE) or BGI ftp ( ftp://ftp.genomics.org.cn/pub/gce).

International audience

Cophylogeny reconciliation is a powerful method for analyzing host-parasite (or host-symbiont) co-evolution. It models co-evolution as an optimization problem where the set of all optimal solutions may represent different biological scenarios which thus need to be analyzed separately. Despite the significant research done in the area, few approaches have addressed the problem of helping the biologist deal with the often huge space of optimal solutions. In this paper, we propose a new approach to tackle this problem. We introduce three different criteria under which two solutions may be considered biologically equivalent, and then we propose polynomial-delay algorithms that enumerate only one representative per equivalence class (without listing all the solutions). Our results are of both theoretical and practical importance. Indeed, as shown by the experiments, we are able to significantly reduce the space of optimal solutions while still maintaining important biological information about the whole space.

MOTIVATION: Phylogenetic tree reconciliation is the method of choice in analyzing host-symbiont systems. Despite the many reconciliation tools that have been proposed in the literature, two main issues remain unresolved: (i) listing suboptimal solutions (i.e. whose score is 'close' to the optimal ones) and (ii) listing only solutions that are biologically different 'enough'. The first issue arises because the optimal solutions are not always the ones biologically most significant; providing many suboptimal solutions as alternatives for the optimal ones is thus very useful. The second one is related to the difficulty to analyze an often huge number of optimal solutions. In this article, we propose Capybara that addresses both of these problems in an efficient way. Furthermore, it includes a tool for visualizing the solutions that significantly helps the user in the process of analyzing the results. AVAILABILITY AND IMPLEMENTATION: The source code, documentation and binaries for all platforms are freely available at https://capybara-doc.readthedocs.io/. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The aim of this paper is to explore the robustness of the parsimonious host-symbiont tree reconciliation method under editing or small perturbations of the input. The editing involves making different choices of unique symbiont mapping to a host in the case where multiple associations exist. This is made necessary by the fact that the tree reconciliation model is currently unable to handle such associations. The analysis performed could however also address the problem of errors. The perturbations are re-rootings of the symbiont tree to deal with a possibly wrong placement of the root specially in the case of fast-evolving species. In order to do this robustness analysis, we introduce a simulation scheme specifically designed for the host-symbiont cophylogeny context, as well as a measure to compare sets of tree reconciliations, both of which are of interest by themselves.

A graph G=(V, E) is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u∈V and there is an edge (u, v)∈E if and only if dmin ≤ dT,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this paper, we focus our attention on PCGs for which the witness tree is a caterpillar. We first give some properties of graphs that are PCGs of a caterpillar. We formulate this problem as an integer linear programming problem and we exploit this formulation to show that for the wheels on n vertices Wn, n=7, …, 11, the witness tree cannot be a caterpillar. Related to this result, we conjecture that no wheel is PCG of a caterpillar. Finally, we state a more general result proving that any PCG admits a full binary tree as witness tree T.

A graph G is called a pairwise compatibility graph (PCG) if there exists an edge-weighted tree T and two non-negative real numbers dmin and dmax such that each leaf lu of T corresponds to a vertex u∈V and there is an edge (u, v)∈E if and only if dmin ≤ dT,w (lu, lv) ≤ dmax, where dT,w (lu, lv) is the sum of the weights of the edges on the unique path from lu to lv in T. In this note, we show that all the graphs with at most seven vertices are PCGs. In particular, all these graphs except for the wheel on seven vertices W7 are PCGs of a particular structure of a tree: a centipede.

A set $\mathcal{F}$ of ordered k-tuples of distinct elements of an n-set is pairwise reverse free if it does not contain two ordered k-tuples with the same pair of elements in the same pair of coordinates in reverse order. Let $F(n,k)$ be the maximum size of a pairwise reverse-free set. In this paper we focus on the case of 3-tuples and prove $\lim F(n,3)/\binom{n}{3}=5/4$, more exactly, $\frac{5}{24}n^3-\frac{1}{2}n^2-O(n\log n)