Consensus pattern Instance: Given a set B of n strings of different lengths and an integer L Objective: Find a string s of length L and for each string S;E B, find a substring t; of s, such that d(s,t Is minimized Theorem: The consensus pattern problem is NP-hard There is a PTAs for consensus pattern(M Li, B Ma, and L Wang, 1999) 2021/1/29 102021/1/29 10 Consensus Pattern Instance: Given a set B of n strings of different lengths, and an integer L, Objective: Find a string s of length L and for each string si  B, find a substring t i of si such that n  d(s, t i ) i=1 is minimized. Theorem: The consensus pattern problem is NP-hard. There is a PTAs for consensus pattern. (M. Li, B. Ma, and L. Wang, 1999)