Abstract The rooted triplet distance measures the structural dissimilarity of two phylogenetic trees or phylogenetic networks by counting the number of rooted phylogenetic trees with exactly three leaf labels (called rooted triplets, or triplets for short) that occur as embedded subtrees in one, but not both, of them. Suppose that $$N_1 = (V_1, E_1)$$ N 1 = ( V 1 , E 1 ) and $$N_2 = (V_2, E_2)$$ N 2 = ( V 2 , E 2 ) are phylogenetic networks over a common leaf label set of size n, that $$N_i$$ N i has level $$k_i$$ k i and maximum in-degree $$d_i$$ d i for $$i \in \{1,2\}$$ i ∈ { 1 , 2 } , and that the networks’ out-degrees are unbounded. Write $$N = \max (|V_1|, |V_2|)$$ N = max ( | V 1 | , | V 2 | ) , $$M = \max (|E_1|, |E_2|)$$ M = max ( | E 1 | , | E 2 | ) , $$k = \max (k_1, k_2)$$ k = max ( k 1 , k 2 ) , and $$d = \max (d_1, d_2)$$ d = max ( d 1 , d 2 ) . Previous work has shown how to compute the rooted triplet distance between $$N_1$$ N 1 and $$N_2$$ N 2 in $$\mathrm {O}(n \log n)$$ O ( n log n ) time in the special case $$k \le 1$$ k ≤ 1 . For $$k > 1$$ k > 1 , no efficient algorithms are known; applying a classic method from 1980 by Fortune et al. in a direct way leads to a running time of $${\Omega

MOTIVATION: Structural variations (SVs) are large scale mutations in a genome; although less frequent than point mutations, due to their large size they are responsible for more heritable differences between individuals. Two prominent classes of SVs are deletions and tandem duplications. They play important roles in many devastating genetic diseases, such as Smith-Magenis syndrome, Potocki-Lupski syndrome and Williams-Beuren syndrome. Since paired-end whole genome sequencing data have become widespread and affordable, reliably calling deletions and tandem duplications has been a major target in bioinformatics; unfortunately, the problem is far from being solved, since existing solutions often offer poor results when applied to real data. RESULTS: We developed a novel caller, SurVIndel, which focuses on detecting deletions and tandem duplications from paired next-generation sequencing data. SurVIndel uses discordant paired reads, clipped reads as well as statistical methods. We show that SurVIndel outperforms existing methods on both simulated and real biological datasets. AVAILABILITY AND IMPLEMENTATION: SurVIndel is available at https://github.com/Mesh89/SurVIndel. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

This article presents two new deterministic algorithms for constructing consensus trees. Given an input of phylogenetic trees with identical leaf label sets and leaves each, the first algorithm constructs the majority rule (+) consensus tree in time, which is optimal since the input size is , and the second one constructs the frequency difference consensus tree in time.