<blockquote>
<p>Why is this approach not used? Are there any algorithms that use it?</p>
</blockquote>
<p>As shown in <a href="https://www.sciencedirect.com/science/article/pii/S0304397597002405" rel="nofollow noreferrer">this paper</a>, the MEDIAN STRING problem is NP-Complete on alphabets of carnality greater than 3. While the problem isn't used directly in approaches due to the complexity, the idea of trying to create a consensus sequence between pairs of input and using that as building blocks is common. These are considered &quot;progressive alignment methods&quot;.</p>

CC BY-SA 4.0
2021-04-21T19:29:19.160Z
2021-04-21T19:29:19.160Z
Throckmorton
<p>I read about the median string problem as an introduction to the multiple sequence alignment, however none of the MSA algorithms used seems to be using the idea of finding the median string.</p>
<p>To my understanding from the consensus (median) string, it would be possible to retrieve the actual alignment by simply doing the pairwise alignment of the consensus string with each of the strings.</p>
<p>Why is this approach not used? Are there any algorithms that use it?</p>
<p>And related to this, what kind of tasks in bioinformatics/biology are median/consensus string algorithms used for?</p>

<phylogenetics><multiple-sequence-alignment>
Median string problem & multiple sequence alignment
# Median string problem & multiple sequence alignment

(Asked by: username_0 on 2021-02-22)

I read about the median string problem as an introduction to the multiple sequence alignment, however none of the MSA algorithms used seems to be using the idea of finding the median string.

To my understanding from the consensus (median) string, it would be possible to retrieve the actual alignment by simply doing the pairwise alignment of the consensus string with each of the strings.

Why is this approach not used? Are there any algorithms that use it?

And related to this, what kind of tasks in bioinformatics/biology are median/consensus string algorithms used for?

**Tags:** phylogenetics, multiple-sequence-alignment

---

## 1 answers

### Answer by username_1 on 2021-04-21. Score: 1

> Why is this approach not used? Are there any algorithms that use it?

As shown in [this paper](https://www.sciencedirect.com/science/article/pii/S0304397597002405), the MEDIAN STRING problem is NP-Complete on alphabets of carnality greater than 3. While the problem isn't used directly in approaches due to the complexity, the idea of trying to create a consensus sequence between pairs of input and using that as building blocks is common. These are considered "progressive alignment methods".


---

