Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction

DOI10.1007/978-3-642-04744-2_5zbMATH Open1333.68138arXiv0912.4196OpenAlexW1516846940MaRDI QIDQ3638844FDOQ3638844

Authors: Cedric Chauve, Utz-Uwe Haus, Tamon Stephen, Vivija P. You 

Publication date: 28 October 2009

Published in: Comparative Genomics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0912.4196

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

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Analysis of algorithms and problem complexity (68Q25) Boolean and Hadamard matrices (15B34)

Cites Work

• 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
• Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
• Bounds on Backtrack Algorithms for Listing Cycles, Paths, and Spanning Trees
• Computational aspects of monotone dualization: a brief survey
• A Simple Test for the Consecutive Ones Property
• A structure theorem for the consecutive 1's property
• Title not available (Why is that?)
• On the consecutive ones property

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)