1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

As shown in this paper, 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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.