The consensus string problem for a metric is NP-complete |
| |
| Authors: | Jeong Seop Sim Kunsoo Park |
| |
| Institution: | a Electronics and Telecommunications Research Institute, Daejeon 305-350, South Korea;b School of Computer Science and Engineering, Seoul National University, Seoul 151-742, South Korea |
| |
| Abstract: | Given a set S of strings, a consensus string of S based on consensus error is a string w that minimizes the sum of the distances between w and all the strings in S. In this paper, we show that the problem of finding a consensus string based on consensus error is NP-complete when the penalty matrix is a metric. |
| |
| Keywords: | Consensus string Multiple sequence alignment NP-complete |
| 本文献已被 ScienceDirect 等数据库收录！ |
