Open Collections

Variants of the Consecutive-Ones Property motivated by the reconstruction of ancestral species

University of British Columbia

The polynomial-time decidable Consecutive-Ones Property (C1P) of binary matrices, formally introduced in 1965 by Fulkerson and Gross, has since found applications in many areas. In this thesis, we propose and study several variants of this property that are motivated by the reconstruction of ancestral species. We first propose the Gapped C1P, or the (k,delta)-C1P: a binary matrix M has the (k,delta)-C1P for integers k and delta if the columns of M can be permuted such that each row contains at most k blocks of 1's and no two neighboring blocks of 1's are separated by a gap of more than delta 0's. The C1P is equivalent to the (1,0)-C1P. We show that for every bounded and unbounded k ≥ 2, delta ≥ 1, (k,delta)≠ (2,1), deciding the (k,delta)-C1P is NP-complete [Golberg et al., 1995]. We also provide an algorithm for a relevant case of the (2,1)-C1P. We then study the (k,delta)-C1P with a bound d on the maximum number of 1's in any row (the maximum degree) of M. We show that the (d,k,delta)-C1P is polynomial-time decidable when all three parameters are fixed constants. Since fixing d also fixes k (k ≤ d), the only case left to consider is the (d,k,infinity)-C1P (when delta is unbounded). We show that for every d > k ≥ 2, deciding the (d,k,infinity)-C1P is NP-complete. We also study the C1P with Multiplicity (mC1P), introduced by Wittler and Stoye [2010]: a binary matrix M on columns S = {1,..,n} has the mC1P for multiplicity vector m:S→ ℕ if there is a sequence sigma on S such that (i) sigma contains each s ∈ S at most m(s) times, and (ii) for each row r of M, the set of columns that have entry 1 in r form at least one subsequence of sigma. We show that deciding the mC1P, and two restricted variants thereof, are NP-complete, for M having maximum degree 3 (6 for one of the variants), and for m(s) ≤ 2 for all s ∈ S. We also give a tractability result for the mC1P that is motivated by handling telomeres in the reconstruction of ancestral species. Finally, we study the Generalized Cladistic Character Compatibility (GCCC) Problem, a generalization of the Perfect Phylogeny Problem [Semple and Steel, 2003] introduced by Benham et al. [1995]. We use the structure of the PQ-tree [Booth and Leuker, 1976] associated with the C1P to give algorithms for several cases of the GCCC Problem.

Text

2012-01-18

Attribution-ShareAlike 3.0 Unported

http://hdl.handle.net/2429/40128

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-sa/3.0/