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.

A regularized iterative algorithm for limited-angle inverse Radon transform

The tomography problem is investigated when the available projections are restricted to a limited angular domain. It is shown that a previous algorithm proposed for extrapolating the data to the missing cone in Fourier space is unstable in the presence of noise because of the ill-posedness of the problem. A regularized algorithm is proposed, which converges to stable solutions. The efficiency of both algorithms is tested by means of numerical simulations. © 1983 Taylor and Francis Group, LLC.

Regularization of an iterative algorithm for the extrapolation of bandlimited signals

info:eu-repo/semantics/published

Study of gene expression in thyrotropin-stimulated thyroid cells by cDNA expression array: ID3 transcription modulating factor as an early response protein and tumor marker in thyroid carcinomas.

Induction of cell proliferation by mitogen or growth factor stimulation leads to the specific induction or repression of a large number of genes. To identify genes differentially regulated by the cAMP-dependent transduction pathway, which is poorly characterized so far, we used the cDNA expression array technology. Hybridizations of Atlas human cDNA expression arrays with (32)P-labeled cDNA probes derived from control or thyrotropin (TSH)-stimulated dog thyrocytes in primary culture generated expression profiles of hundreds of genes simultaneously. Among the genes that displayed modified expression, we selected the transcription factor ID3, whose expression was increased by a cAMP-dependent stimulus. ID3 overexpression after TSH stimulation was first verified by Northern blotting analysis, and its mRNA regulation was then investigated in response to a variety of agents acting on thyrocyte proliferation and/or differentiation. We show that: (1) ID3 mRNA induction was stronger after stimulation of the cAMP cascade, but was not restricted to this signaling pathway, as phorbol myristate ester (TPA) and insulin also stimulated mRNA accumulation; (2) in contrast, powerful mitogens for thyroid cells, epidermal growth factor and hepatocyte growth factor, did not significantly modify ID3 mRNA levels; (3) ID3 protein levels closely parallelled mRNA levels, as revealed by immunofluorescence experiments showing a nuclear signal regulated by TSH; (4) in papillary thyroid carcinomas, ID3 mRNA was downregulated. Our results suggest that ID3 expression might be more related to the differentiating process induced by TSH than to the proliferative action of this hormone.