A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each row are consecutive. Algorithmic issues of the C1P are central in computational molecular biology, in particular for physical mapping and ancestral genome reconstruction. In 1972, Tucker gave a characterization of matrices that have the C1P by a set of forbidden submatrices, and a substantial amount of research has been devoted to the problem of efficiently finding such a minimum size forbidden submatrix. This paper presents a new O(Δ^3 m 2 (mΔ + n^3)) time algorithm for this particular task for a m ×n binary matrix with at most Δ 1-entries per row, thereby improving the O(Δ^3 m 2(mn + n^3)) time algorithm of Dom et al. [17].

A Faster Algorithm for Finding Minimum Tucker Submatrices.

RIZZI, ROMEO;
2010-01-01

Abstract

A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1s on each row are consecutive. Algorithmic issues of the C1P are central in computational molecular biology, in particular for physical mapping and ancestral genome reconstruction. In 1972, Tucker gave a characterization of matrices that have the C1P by a set of forbidden submatrices, and a substantial amount of research has been devoted to the problem of efficiently finding such a minimum size forbidden submatrix. This paper presents a new O(Δ^3 m 2 (mΔ + n^3)) time algorithm for this particular task for a m ×n binary matrix with at most Δ 1-entries per row, thereby improving the O(Δ^3 m 2(mn + n^3)) time algorithm of Dom et al. [17].
2010
9783642139611
Consecutive Ones Property (C1P); forbidden submatrix; Tucker's submatrix; algorithm; computational molecular biology; physical mapping; ancestral genome reconstruction
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/409560
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 4
social impact