Preprints by Winfried Just

This web page contains abstracts and links to some of my papers that for a variety of reasons I did not (yet) decide to publish in more traditional venues.

On the computational complexity of gap-0 multiple alignment. May 25, 1999. Version posted here has been updated on September 4, 1999.

Multiple alignment of nucleotide or amino acid sequences is a fundamental process in molecular biology. Sequences can be aligned by shifting them relative to each other and by inserting spaces. It had been known for some time that the problem of finding the multiple alignment with optimal score is NP-hard in the number of sequences at least for some scoring matrices. It is shown here that for certain scoring matrices the seemingly simpler problem of finding the multiple alignment with optimum score that can be achieved by shifting sequences relative to each other, but not inserting spaces (the "gap-0 multiple alignment problem") is still NP-hard in the number of sequences. The proof uses a reduction of the bounded MAX-2SAT problem to the gap-0 multiple alignment problem. These results have been superseded by the paper Computational complexity of multiple sequence alignment with SP-score, where a different and more elegant reduction is used to show that both the multiple alignment problem and the gap-0 multiple alignment problem are NP-hard for the scoring matrices that are used in actual biological applications.

dvi file postscript file
Reducing gap-0 multiple alignment to multiple alignment. June 7, 1999.

A sequel to preprint number 1. It is shown how results on gap-0 multiple alignment can be used to derive analogous results for the unrestricted multiple alignment problem. This paper has been superseded by the stronger results and more elegant proof of Computational complexity of multiple sequence alignment with SP-score.

dvi file postscript file
An Ostaszewski-type space. November 28, 1999.

Part of lecture notes for a graduate course on combinatorial principles and forcing that I taught in 1998/99.
The Juhasz club principle is defined and details of a construction of a first countable, locally countable, locally compact Dowker S-space of size w₁ from the Juhasz club principle are worked out. A problem of Szeptycki and Weiss is solved.

dvi file postscript file
A unified approach to $\diamondsuit$-like principles. November 28, 1999.

Part of lecture notes for a graduate course on combinatorial principles and forcing that I taught in 1998/99.
A generalization of the diamond-principle is defined and it is shown that this generalization subsumes many known diamond-like principles as special cases.

dvi file postscript file