Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction

Details Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction

2009-12-21

arxiv.org/abs/0912.4196v1

J Comput Biol. 2010 Sep;17(9):1167-81

Biology

Quantitative Biology

Genomics

20 pages, 3 figures

Scientific paper

10.1089/cmb.2010.0113

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.

Affiliated with

Also associated with

No associations

Rating

Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimal Conflicting Sets for the Consecutive Ones Property in ancestral genome reconstruction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-302944