Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction
From MaRDI portal
Publication:3638844
Abstract: A binary matrix has the Consecutive Ones Property (C1P) if its columns can be ordered in such a way that all 1's on each row are consecutive. A Minimal Conflicting Set is a set of rows that does not have the C1P, but every proper subset has the C1P. Such submatrices have been considered in comparative genomics applications, but very little is known about their combinatorial structure and efficient algorithms to compute them. We first describe an algorithm that detects rows that belong to Minimal Conflicting Sets. This algorithm has a polynomial time complexity when the number of 1's in each row of the considered matrix is bounded by a constant. Next, we show that the problem of computing all Minimal Conflicting Sets can be reduced to the joint generation of all minimal true clauses and maximal false clauses for some monotone boolean function. We use these methods on simulated data related to ancestral genome reconstruction to show that computing Minimal Conflicting Set is useful in discriminating between true positive and false positive ancestral syntenies. We also study a dataset of yeast genomes and address the reliability of an ancestral genome proposal of the Saccahromycetaceae yeasts.
Recommendations
- Minimum mosaic inference of a set of recombinants
- Reconstructing an ancestral genome using minimum segments duplications and reversals.
- On the number of non-equivalent ancestral configurations for matching gene trees and species trees
- Improved Algorithms for Inferring the Minimum Mosaic of a Set of Recombinants
- Minimal Triangulation Algorithms for Perfect Phylogeny Problems
- Bounds on the minimum mosaic of population sequences under recombination
- Ancestral sequence reconstruction with maximum parsimony
- Minimum interval cover and its application to genome sequencing
Cites work
- scientific article; zbMATH DE number 1003281 (Why is no real title available?)
- A Simple Test for the Consecutive Ones Property
- A structure theorem for the consecutive 1's property
- Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
- Computational aspects of monotone dualization: a brief survey
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- On the consecutive ones property
- Random generation of combinatorial structures from a uniform distribution
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- The Complexity of Enumeration and Reliability Problems
Cited in
(6)- A faster algorithm for finding minimum Tucker submatrices
- Hardness results on the gapped consecutive-ones property problem
- A polynomial-time algorithm for finding a minimal conflicting set containing a given row
- Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
- The minimum conflict-free row split problem revisited
- Faster and simpler minimal conflicting set identification (extended abstract)
This page was built for publication: Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638844)
