Part of the book series:Lecture Notes in Computer Science ((LNBI,volume 6398))
Included in the following conference series:
747Accesses
Abstract
The Gapped Consecutive-Ones Property (C1P) Problem, or the (k,δ)-C1P Problem is: given a binary matrixM and integersk andδ, decide if the columns ofM can be ordered such that each row contains at mostk blocks of1’s, and no two neighboring blocks of1’s are separated by a gap of more thanδ0’s. This problem was introduced in [3]. The classical polynomial-time solvable C1P Problem is equivalent to the (1,0)-C1P problem. It has been shown that for every unbounded or boundedk ≥ 2 and unbounded or boundedδ ≥ 1, except when (k,δ) = (2,1), the (k,δ)-C1P Problem is NP-complete [10,6].
In this paper we study the Gapped C1P Problem with a third parameterd, namely the bound on the maximum number of1’s in any row ofM, or the bound on the maximumdegree ofM. This is motivated by problems in comparative genomics and paleogenomics, where the genome data is often sparse [4]. The (d,k,δ)-C1P Problem has been shown to be polynomial-time solvable when all three parameters are fixed [3]. Since fixingd also fixesk (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 everyd > k ≥ 2, the (d,k, ∞ )-C1P Problem is NP-complete.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alizadeh, F., Karp, R., Weisser, D., Zweig, G.: Physical mapping of chromosomes using unique probes. J. Comput. Biol. 2(2), 159–184 (1995)
Chauve, C., Haus, U.W., Stephen, T., You, V.P.: Minimal conflicting sets for the consecutive-ones property in ancestral genome reconstruction. In: Ciccarelli, F.D., Miklós, I. (eds.) RECOMB-CG 2009. LNCS (LNBI), vol. 5817, pp. 48–58. Springer, Heidelberg (2009)
Chauve, C.: Maňuch, J., Patterson, M.: On the gapped consecutive-ones property. In: Proc. of European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB). ENDM, vol. 34, pp. 121–125 (2009)
Chauve, C., Tannier, E.: A methodological framework for the reconstruction of contiguous regions of ancestral genomes and its application to mammalian genomes. PLoS Comput. Biol. 4, e1000234 (2008)
Dom, M.: Recognition, generation, and application of binary matrices with the consecutive-ones property. Ph.D. thesis, Institut für Informatik, Friedrich-Schiller-Universität, Jena (2008)
Goldberg, P., Golumbic, M., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. J. Comput. Biol. 2(1), 139–152 (1995)
Gupta, A., Maňuch, J., Stacho, L., Zhao, X.: Algorithm for haplotype inferring via galled-tree networks with simple galls. In: Măndoiu, I.I., Zelikovsky, A. (eds.) ISBRA 2007. LNCS (LNBI), vol. 4463, pp. 121–132. Springer, Heidelberg (2007)
Gupta, A., Maňuch, J., Stacho, L., Zhao, X.: Haplotype inferring via galled-tree networks is NP-complete. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol. 5092, pp. 287–298. Springer, Heidelberg (2008)
Gupta, A., Maňuch, J., Stacho, L., Zhao, X.: Haplotype inferring via galled-tree networks using a hypergraph covering problem for special genotype matrices. Discr. Appl. Math. 157(10), 2310–2324 (2009)
Maňuch, J., Patterson, M., Chauve, C.: Hardness results for the gapped C1P problem (unpublished manuscript)
McConnell, R.M.: A certifying algorithm for the consecutive-ones property. In: Proc. of Symposium on Discrete Algorithms (SODA), pp. 761–770. SIAM, Philadelphia (2004)
Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)
Saxe, J.B.: Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. on Alg. and Discr. Meth. 1(4), 363–369 (1980)
Tucker, A.C.: A structure theorem for the consecutive 1’s property. J. of Comb. Theory, Series B 12, 153–162 (1972)
Author information
Authors and Affiliations
Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada
Ján Maňuch
Deptartment of Computer Science, UBC, Vancouver, BC, Canada
Ján Maňuch & Murray Patterson
- Ján Maňuch
You can also search for this author inPubMed Google Scholar
- Murray Patterson
You can also search for this author inPubMed Google Scholar
Editor information
Editors and Affiliations
INRIA Rhône-Alpes, Université de Lyon 1, Villeurbanne, France
Eric Tannier
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Maňuch, J., Patterson, M. (2010). The Complexity of the Gapped Consecutive-Ones Property Problem for Matrices of Bounded Maximum Degree. In: Tannier, E. (eds) Comparative Genomics. RECOMB-CG 2010. Lecture Notes in Computer Science(), vol 6398. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16181-0_23
Download citation
Publisher Name:Springer, Berlin, Heidelberg
Print ISBN:978-3-642-16180-3
Online ISBN:978-3-642-16181-0
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative