Scholars Central

EditorialPublished Jan 2021

Quasi-Optimal Multiple Sequence Alignments

Authors: Quoc-Nam Tran, Mike Wallinga

Ask about this article

Abstract

Select any words in the title or abstract, or press this and choose a sentence.

Finding an optimal multiple sequence alignment (MSA) of three or more nucleic acid or amino acid sequences is a fundamental problem of bioinformatics with a large number of publications and citations over the last 30 years. Given a set of sequences, an optimal MSA identifies homologous characters, which have common ancestry. The resulting MSA is used for many downstream applications in medical and health informatics such as constructing phylogenetic trees, finding protein families, predicting secondary and tertiary structure of new sequences, and demonstrating the homology between new sequences and existing families. Unfortunately, techniques that work well for pairwise alignment often become too computationally expensive when they are applied to multiple sequence alignment due the extremely large size of the search space. In fact, it is common for multiple sequence alignment problems to become computationally intractable. This is because multiple sequence alignment is a combinatorial problem, and as the number or size of the sequences in the problem set increases, the computational time required performing an alignment increases exponentially. That is, for n sequences of length l, computing the optimal alignment exactly carries a computational complexity of O(ln). Thus, dynamic programming techniques such as the Needleman-Wunsch algorithm are guaranteed to produce optimal solutions to multiple sequence alignment problems, but are generally impractical for all but the smallest examples. In fact, multiple sequence alignment algorithms using the sum-of-pair heuristic is NP-complete. As a result, most currently-employed multiple sequence alignment algorithms are based on heuristics and must settle for providing a quasi-optimal alignment. In this editorial article, we will summarize the previous works on MSA especially some recent computational methods for quasioptimal multiple sequence alignments. We will also discuss some possible approaches for future works.

Ask about this article

Answers come only from this article's title, abstract and keywords, each sentence pointing to where it comes from. Your question is sent to OpenAI to write the answer. Scholars Central does not store it.

Try:

Similar by topic

More from this journal

The newest in Journal of Health Informatics & Management.

All its articles

Conferences in this field

Upcoming conferences in this field.

Follow

New articles from what you follow go into your email digest, once you agree to alert emails.

  • JournalJournal of Health Informatics & Management
  • SubjectComputer Science & IT
  • BylineArticles whose byline prints “Quoc-Nam Tran”
  • BylineArticles whose byline prints “Mike Wallinga”

For authors and organisers

Publish, present and keep up with your field

Find the right journal for your paper and submit your manuscript.

Photo: Pexels