Characterisation: conservation problem C2

• Given a set S+ of sequences believed to be members of family F+, i.e. S+ ? F+

• Find interesting string functions that return

  • TRUE for all s ? S+
  • have a high likelihood for returning TRUE for s ? F+

• N2: suppose F+ ? ?*, and given S+ ? ?*, such that S+ ? (F+)- is small, find interesting string functions that return

  • TRUE for most s ? S+, and
  • have a high likelihood for returning TRUE for s ? F+

• Interesting: have a low probability for returning TRUE for random sequences

Previous slide

Next slide

Back to first slide

View graphic version