Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ron Shamir:

TR01-054 | 12th April 2001
Amir Ben-Dor, Itsik Pe'er, Roded Sharan, Ron Shamir

On the Complexity of Positional Sequencing by Hybridization

In sequencing by hybridization (SBH),
one has to reconstruct a sequence
from its $l$-long substrings.
SBH was proposed as
an alternative to
DNA sequencing approaches, but in its original form the method
not competitive.
Positional SBH (PSBH) is a recently proposed
enhancement ... more >>>

TR98-071 | 26th November 1998
Itsik Pe'er, Ron Shamir

The median problems for breakpoints are NP-complete

The breakpoint distance between two $n$-permutations is the number
of pairs that appear consecutively in one but not in the other. In
the median problem for breakpoints one is given a set of
permutations and has to construct a permutation that minimizes the
sum of breakpoint ... more >>>

ISSN 1433-8092 | Imprint