Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.

Comparison of the thermodynamics and base-pair dynamics of a full LNA:DNA duplex and of the isosequential DNA:DNA duplex

Locked nucleic acids (LNA), conformationally restricted nucleotide analogues, are known to enhance pairing stability and selectivity toward complementary strands. With the aim to contribute to a better understanding of the origin of these effects, the structure, thermal stability, hybridization thermodynamics, and base-pair dynamics of a full-LNA:DNA heteroduplex and of its isosequential DNA:DNA homoduplex were monitored and compared. CD measurements highlight differences in the duplex structures: the homoduplex and heteroduplex present B-type and A-type helical conformations, respectively. The pairing of the hybrid duplex is characterized, at all temperatures monitored (between 15 and 37 degrees C), by a larger stability constant but a less favorable enthalpic term. A major contribution to this thermodynamic profile emanates from the presence of a hairpin structure in the LNA single strand which contributes favorably to the entropy of interaction but leads to an enthalpy penalty upon duplex formation. The base-pair opening dynamics of both systems was monitored by NMR spectroscopy via imino protons exchange measurements. The measurements highlight that hybrid G-C base-pairs present a longer base-pair lifetime and higher stability than natural G-C base-pairs, but that an LNA substitution in an A-T base-pair does not have a favorable effect on the stability. The thermodynamic and dynamic data confirm a more favorable stacking of the bases in the hybrid duplex. This study emphasizes the complementarities between dynamic and thermodynamical studies for the elucidation of the relevant factors in binding events.