In 2014, Hajirasouliha and Raphael proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number of rows among all matrices with this property. In this paper, we disprove several claims about this problem, including an NP-hardness proof of it. However, we show that the problem is indeed NP-hard, by providing a different proof. On the positive side, we propose an efficient (though not necessarily optimal) heuristic algorithm based on coloring co-comparability graphs, and a polynomial time algorithm for solving the problem optimally on matrix instances in which no column is contained in both columns of a pair of conflicting columns. Implementations of these algorithms are freely available at https://github.com/alexandrutomescu/MixedPerfectPhylogeny.
COBISS.SI-ID: 1538780868
Mathematical evolutionary models suggest that reputation is required for stable cooperation. In this article we compare the relative importance of 1st- (what someone did) and 2nd-order (why someone did) reputation. With a behavioral experiment, we study whether people apply simple heuristics. Most of them do, and a substantial fraction consistently consider the 2nd-order information.
COBISS.SI-ID: 1538835908
All regular Cayley maps on dihedral group D_n, n)1, of order 2n are classified. Besides 4 sporadic maps on 4,4,8 and 12 vertices respectively, two infinite families of non-t-balanced Cayley maps on D_n are obtained.
COBISS.SI-ID: 1538922180
A positive integer n is a Cayley number if every vertex-transitive graph of order n is a Cayley graph. In 1983, Dragan Marušič posed the problem of determining the Cayley numbers. In this paper we give an infinite set S of primes such that every finite product of distinct elements from S is a Cayley number. This answers a 1996 outstanding question of Brendan McKay and Cheryl Praeger, which they “believe to be the key unresolved question” on Cayley numbers. We also show that, for every finite product n of distinct elements from S, every transitive group of degree n contains a semiregular element.
COBISS.SI-ID: 1538528196
The following problem is considered: if H is a semiregular abelian subgroup of a transitive permutation group G acting on a finite set X, find conditions for (non)existence of G -invariant partitions of X. Conditions presented in this paper are derived by studying spectral properties of associated G -invariant digraphs. As an essential tool, irreducible complex characters of H are used. Questions of this kind arise naturally when classifying combinatorial objects which enjoy a certain degree of symmetry. As an illustration, a new and short proof of an old result of Frucht et al. (Proc Camb Philos Soc 70:211–218, 1971) classifying edge- transitive generalized Petersen graphs, is given.
COBISS.SI-ID: 1536772036