Physical Sciences and Mathematics Commons^™

Probabilistic Analysis Of A Motif Discovery Algorithm For Multiple Sequences, Bin Fu, Ming-Yang Kao, Lusheng Wang

Computer Science Faculty Publications and Presentations

We study a natural probabilistic model for motif discovery that has been used to experimentally test the quality of motif discovery programs. In this model, there are k background sequences, and each character in a background sequence is a random character from an alphabet Σ. A motif G = g1g2 · · · gm is a string of m characters. Each background sequence is implanted into a probabilistically generated approximate copy of G. For an approximate copy b1b2 · · · bm of G, every character bi is probabilistically generated such that the probability for r $b_i\neq g_i$ is at …

The Informational Content Of Canonical Disjoint Np-Pairs, Christian Glaßer, Alan L. Selman, Liyu Zhang

Computer Science Faculty Publications and Presentations

We investigate the connection between propositional proof systems and their canonical pairs. It is known that simulations between propositional proof systems translate to reductions between their canonical pairs. We focus on the opposite direction and study the following questions.

Q1: For which propositional proof systems f and g does the implication hold, and for which does it fail?

Q2: For which propositional proof systems of different strengths are the canonical pairs equivalent?

Q3: What do (non-)equivalent canonical pairs tell about the corresponding propositional proof systems?

Q4: Is every NP-pair (A, B), where A is NP-complete, strongly many-one equivalent to the …