Improved algorithms for the multicut and multiflow problems in rooted trees

Costa et al. (Oper. Res. Lett. 31:21–27, 2003) presented a quadratic O(min (Kn,n ²)) greedy algorithm to solve the integer multicut and multiflow problems in a rooted tree. (n is the number of nodes of the tree, and K is the number of commodities). Their algorithm is a special case of the greedy type algorithm of Kolen (Location problems on trees and in the rectilinear plane. Ph.D. dissertation, 1982) to solve weighted covering and packing problems defined by general totally balanced (greedy) matrices. In this communication we improve the complexity bound in Costa et al. (Oper. Res. Lett. 31:21–27, 2003) and show that in the case of the integer multicut and multiflow problems in a rooted tree the greedy algorithm of Kolen can be implemented in subquadratic O(K+n+min (K,n)log n) time. The improvement is obtained by identifying additional properties of this model which lead to a subquadratic transformation to greedy form and using more sophisticated data structures.      

An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen by unequal recombination, was first introduced by Fitch (1977), and has recently received a lot of attention. In this paper, we place ourselves in a distance framework and deal with the restricted problem of reconstructing single copy duplication trees. We describe an exact and polynomial distance based algorithm for solving this problem, the parsimony version of which has previously been shown to be NP-hard (like most evolutionary tree reconstruction problems). This algorithm is based on the minimum evolution principle, and thus involves selecting the shortest tree as being the correct duplication tree. After presenting the underlying mathematical concepts behind the minimum evolution principle, and some of its benefits (such as statistical consistency), we provide a new recurrence formula to estimate the tree length using ordinary least-squares, given a matrix of pairwise distances between the copies. We then show how this formula naturally forms the dynamic programming framework on which our algorithm is based, and provide an implementation in O(n³) time and O(n²) space, where n is the number of copies.     

Characterization of complex networks by higher order neighborhood properties

A concept of higher order neighborhood in complex networks, introduced previously [Phys. Rev. E 73, 046101 (2006)], is systematically explored to investigate larger scale structures in complex networks. The basic idea is to consider each higher order neighborhood as a network in itself, represented by a corresponding adjacency matrix, and to settle a plenty of new parameters in order to obtain a best characterization of the whole network. Usual network indices are then used to evaluate the properties of each neighborhood. The identification of high order neighborhoods is also regarded as intermediary step towards the evaluation of global network properties, like the diameter, average shortest path between node, and network fractal dimension. Results for a large number of typical networks are presented and discussed.     

Dendriform equations

We investigate solutions for a particular class of linear equations in dendriform algebras. Motivations as well as several applications are provided. The latter follow naturally from the intimate link between dendriform algebras and Rota–Baxter operators, e.g. the Riemann integral map or Jackson's q-integral.     

Random forests for functional covariates

We propose a form of random forests that is especially suited for functional covariates. The method is based on partitioning the functions' domain in intervals and using the functions' mean values across those intervals as predictors in regression or classification trees. This approach appears to be more intuitive to applied researchers than usual methods for functional data, while also performing very well in terms of prediction accuracy. The intervals are obtained from randomly drawn, exponentially distributed waiting times. We apply our method to data from Raman spectra on boar meat as well as near‐infrared absorption spectra. The predictive performance of the proposed functional random forests is compared with commonly used parametric and nonparametric functional methods and with a nonfunctional random forest using the single measurements of the curve as covariates. Further, we present a functional variable importance measure, yielding information about the relevance of the different parts of the predictor curves. Our variable importance curve is much smoother and hence easier to interpret than the one obtained from nonfunctional random forests.     

On the Tutte–Krushkal–Renardy polynomial for cell complexes

Recently V. Krushkal and D. Renardy generalized the Tutte polynomial from graphs to cell complexes. We show that evaluating this polynomial at the origin gives the number of cellular spanning trees in the sense of A. Duval, C. Klivans, and J. Martin. Moreover, after a slight modification, the Tutte–Krushkal–Renardy polynomial evaluated at the origin gives a weighted count of cellular spanning trees, and therefore its free term can be calculated by the cellular matrix-tree theorem of Duval et al. In the case of cell decompositions of a sphere, this modified polynomial satisfies the same duality identity as the original polynomial. We find that evaluating the Tutte–Krushkal–Renardy along a certain line gives the Bott polynomial. Finally we prove skein relations for the Tutte–Krushkal–Renardy polynomial.     

Psi‐series method for equality of random trees and quadratic convolution recurrences

An unusual and surprising expansion of the form as , is derived for the probability p_n that two randomly chosen binary search trees are identical (in shape, hence in labels of all corresponding nodes). A quantity arising in the analysis of phylogenetic trees is also proved to have a similar asymptotic expansion. Our method of proof is new in the literature of discrete probability and the analysis of algorithms, and it is based on the logarithmic psi‐series expansions for nonlinear differential equations. Such an approach is very general and applicable to many other problems involving nonlinear differential equations; many examples are discussed in this article and several attractive phenomena are discovered.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 67–108, 2014     

Gene tree correction for reconciliation and species tree inference: Complexity and algorithms

Reconciliation consists in mapping a gene tree T into a species tree S, and explaining the incongruence between the two as evidence for duplication, loss and other events shaping the gene family represented by the leaves of T. When S is unknown, the Species Tree Inference Problem is to infer, from a set of gene trees, a species tree leading to a minimum reconciliation cost. As reconciliation is very sensitive to errors in T, gene tree correction prior to reconciliation is a fundamental task. In this paper, we investigate the complexity of four different combinatorial approaches for deleting misplaced leaves from T. First, we consider two problems (Minimum Leaf Removal and Minimum Species Removal) related to the reconciliation of T with a known species tree S. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) so that T is “MD-consistent” with S. Second, we consider two problems (Minimum Leaf Removal Inference and Minimum Species Removal Inference) related to species tree inference. In the former (latter respectively) we want to remove the minimum number of leaves (species respectively) from T so that there exists a species tree S such that T is MD-consistent with S. We prove that Minimum Leaf Removal and Minimum Species Removal are APX-hard, even when each label has at most two occurrences in the input gene tree, and we present fixed-parameter algorithms for the two problems. We prove that Minimum Leaf Removal Inference is not only NP-hard, but also W[2]-hard and inapproximable within factor $c\ln n$, where n is the number of leaves in the gene tree. Finally, we show that Minimum Species Removal Inference is NP-hard and W[2]-hard, when parameterized by the size of the solution, that is the minimum number of species removals.