Research article · 2013
EditorialPublished Jul 2020
Quasi-Optimal Multiple Sequence Alignments
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 multi- ple 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 to perform 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-pairs 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.
Subjects
Computer Science & ITAsk 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.
Similar by topic
Review article · 17 Dec 2017
A Novel Method for Multiple Sequence Alignment Using Morphing Techniques
Research article · 2013
SAM-Profiler: A Graphical Tool for Qualitative Profiling of Next Generation Sequencing Alignment Data
Mini review · 31 Dec 2022
Multiple DNA/RNA sequence alignment and phylogenetic tree-building programme called SaAlign for extremely huge datasets and extremely lengthy sequences
Research article · 24 Jun 2016
Multiple sequence alignment based on combining genetic algorithm with chaotic sequences
More from this journal
The newest in Journal of Health Informatics & Management.
Perspective · 25 Mar 2025
Advancements in Health Information Systems: A Comprehensive Review
Perspective · 25 Mar 2025
Data Analytics in Healthcare Management: Challenges and Opportunities
Perspective · 25 Mar 2025
Women's Health: From Diagnosis to Treatment and Beyond
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”

