The Gapped Consecutive-Ones Property (C1P) Problem, or the (k, δ)-C1P Problem is: given a binary matrix M and integers k and δ, decide if the columns of M can be ordered 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 δ 0's. This problem was introduced by Chauve et al. (2009b). The classical polynomial-time solvable C1P Problem is equivalent to the (1, 0)-C1P problem. It has been shown that, for every unbounded or bounded k≥2 and unbounded or bounded δ≥1, except when (k, δ)=(2, 1), the (k, δ)-C1P Problem is NP-complete (Maňuch et al., 2011; Goldberg et al., 1995). In this article, we study the Gapped C1P Problem with a third parameter d, namely the bound on the maximum number of 1's in any row of M, or the bound on the maximum degree of M. This is motivated by the reconstruction of ancestral genomes (Ma et al., 2006; Chauve and Tannier, 2008), where, in binary matrices obtained from the experiments of Chauve and Tannier (2008), we have observed that the majority of the rows have low degree, while each high degree row contains many rows of low degree. The (d, k, δ)-C1P Problem has been shown to be polynomial-time solvable when all three parameters are fixed (Chauve et al., 2009b). Since fixing d also fixes k (k≤d), the only case left to consider is the case when δ is unbounded, or the (d, k, δ)-C1P Problem. Here we show that for every d&gt;k≥2, the (d, k, δ)-C1P Problem is NP-complete. © 2011, Mary Ann Liebert, Inc

Maňuch, J., Patterson, M. (2011). The complexity of the gapped consecutive-ones property problem for matrices of bounded maximum degree. JOURNAL OF COMPUTATIONAL BIOLOGY, 18(9), 1243-1253 [10.1089/cmb.2011.0128].

### The complexity of the gapped consecutive-ones property problem for matrices of bounded maximum degree

#### Abstract

The Gapped Consecutive-Ones Property (C1P) Problem, or the (k, δ)-C1P Problem is: given a binary matrix M and integers k and δ, decide if the columns of M can be ordered 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 δ 0's. This problem was introduced by Chauve et al. (2009b). The classical polynomial-time solvable C1P Problem is equivalent to the (1, 0)-C1P problem. It has been shown that, for every unbounded or bounded k≥2 and unbounded or bounded δ≥1, except when (k, δ)=(2, 1), the (k, δ)-C1P Problem is NP-complete (Maňuch et al., 2011; Goldberg et al., 1995). In this article, we study the Gapped C1P Problem with a third parameter d, namely the bound on the maximum number of 1's in any row of M, or the bound on the maximum degree of M. This is motivated by the reconstruction of ancestral genomes (Ma et al., 2006; Chauve and Tannier, 2008), where, in binary matrices obtained from the experiments of Chauve and Tannier (2008), we have observed that the majority of the rows have low degree, while each high degree row contains many rows of low degree. The (d, k, δ)-C1P Problem has been shown to be polynomial-time solvable when all three parameters are fixed (Chauve et al., 2009b). Since fixing d also fixes k (k≤d), the only case left to consider is the case when δ is unbounded, or the (d, k, δ)-C1P Problem. Here we show that for every d>k≥2, the (d, k, δ)-C1P Problem is NP-complete. © 2011, Mary Ann Liebert, Inc
##### Scheda breve Scheda completa Scheda completa (DC)
Articolo in rivista - Articolo scientifico
Ancestral genome; computational complexity; consecutive-ones property; hypergraph covering; reconstruction; Algorithms; Computer Simulation; Evolution, Molecular; Mutation; Models, Genetic; Models, Statistical; Modeling and Simulation; Molecular Biology; Genetics; Computational Mathematics; Computational Theory and Mathematics
English
2011
18
9
1243
1253
reserved
Maňuch, J., Patterson, M. (2011). The complexity of the gapped consecutive-ones property problem for matrices of bounded maximum degree. JOURNAL OF COMPUTATIONAL BIOLOGY, 18(9), 1243-1253 [10.1089/cmb.2011.0128].
File in questo prodotto:
File
Maňuch-2011-J Computat Biol-VoR.pdf

Solo gestori archivio

Descrizione: Research Article
Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Licenza: Tutti i diritti riservati
Dimensione 436.26 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/10281/217375`