 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Variants of the ConsecutiveOnes Property motivated...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Variants of the ConsecutiveOnes Property motivated by the reconstruction of ancestral species Patterson, Murray
Abstract
The polynomialtime decidable ConsecutiveOnes 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 NPcomplete [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 polynomialtime 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 NPcomplete. 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 NPcomplete, 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 PQtree [Booth and Leuker, 1976] associated with the C1P to give algorithms for several cases of the GCCC Problem.
Item Metadata
Title 
Variants of the ConsecutiveOnes Property motivated by the reconstruction of ancestral species

Creator  
Publisher 
University of British Columbia

Date Issued 
2012

Description 
The polynomialtime decidable ConsecutiveOnes 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 NPcomplete [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 polynomialtime 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 NPcomplete.
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 NPcomplete, 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 PQtree [Booth and Leuker, 1976] associated with the C1P to give algorithms for several cases of the GCCC Problem.

Genre  
Type  
Language 
eng

Date Available 
20120118

Provider 
Vancouver : University of British Columbia Library

Rights 
AttributionShareAlike 3.0 Unported

DOI 
10.14288/1.0052159

URI  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Graduation Date 
201205

Campus  
Scholarly Level 
Graduate

Rights URI  
Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
AttributionShareAlike 3.0 Unported