On the Complexity of Multiple Sequence Alignment

No abstract is available for this paper.

• Publication year

  1994

• Venue

  J. Comput. Biol.

• Publication date

  1994-12-01

• Fields of study

  Biology, Mathematics, Computer Science, Medicine

• Identifiers
  DOI 10.1089/cmb.1994.1.337PMID 8790475
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• More on the Complexity of Common Superstring and Supersequence Problems

  1994cited by this paper
• Efficient methods for multiple sequence alignment with guaranteed error bounds

  1993influential reference
• Mapping the genome: some combinatorial problems arising in molecular biology

  1993cited by this paper
• A robust model for finding optimal evolutionary trees

  1993cited by this paper
• Improved approximations for the Steiner tree problem

  1992influential reference
• MULTIPLE ALIGNMENT , COMMUNICATION COST , AND GRAPH MATCHING *

  1992cited by this paper
• A survey of multiple sequence comparison methods.

  1992cited by this paper
• A workbench for multiple alignment construction and analysis

  1991cited by this paper
• Optimization, approximation, and complexity classes

  1991influential reference
• Mapping and interpreting biological information

  1991cited by this paper
• Mathematical Methods for DNA Sequences

  1989cited by this paper
• A tree reconstruction method that is economical in the number of pairwise comparisons used.

  1989cited by this paper
• A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given.

  1989cited by this paper
• Trees, stars, and multiple biological sequence alignment

  1989cited by this paper
• The multiple sequence alignment problem in biology

  1988cited by this paper
• Multiple sequence alignment.

  1986cited by this paper
• Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison

  1983cited by this paper
• The steiner problem in phylogeny is NP-complete

  1982influential reference
• Evolution of Protein Molecules

  1979cited by this paper
• Frequency of insertion-deletion, transversion, and transition in the evolution of 5S ribosomal RNA

  1976cited by this paper
• Minimal Mutation Trees of Sequences

  1975cited by this paper

• MuSAlS: A Fast Multiple Sequence Alignment Approach Using Hierarchical Clustering

  2026cites this paper
• A deep-learning-based score to evaluate multiple sequence alignments

  2026cites this paper
• MAFFT-inspired Quantum Shift-based Sequence Alignment and its Efficient Simulation on Decision Diagrams

  2026cites this paper
• A Survey on Sequence Alignment Algorithms and State-of-the-Art Aligners

  2025cites this paper
• Workflow para Alinhamento Exato de Sequências em Sistemas de Processamento de Alto Desempenho

  2025cites this paper
• Derivation of optimal sequence alignment using quantum annealing

  2025cites this paper
• Evolutionary Reasoning Does Not Arise in Standard Usage of Protein Language Models

  2025cites this paper
• Scalable Guide Tree Construction Using Quantum Annealing for Multiple Sequence Alignment

  2025cites this paper
• A multi-objective evolutionary algorithm for improving the iterative search of MAFFT

  2025cites this paper
• Automated Genomic Interpretation via Concept Bottleneck Models for Medical Robotics

  2025cites this paper
• PA-Star2: Fast Optimal Multiple Sequence Alignment for Asymmetric Multicore Processors

  2025cites this paper
• Regression Models for Estimating Similarity Score of the Optimal Expected Multiple Sequence Alignments

  2025cites this paper
• ET-Pfam: Ensemble transfer learning for protein family prediction

  2025cites this paper
• Paralelização da Geração de Constraints Lists em Alinhamentos Múltiplos de Sequências Genéticas

  2025cites this paper
• Multiple Alignments of Protein Families with Weak Sequence Similarity Within the Family

  2025cites this paper
• Ali-U-Net: A Convolutional Transformer Neural Net for Multiple Sequence Alignment of DNA Sequences. A proof of concept

  2025cites this paper
• LIMO: Low-power in-memory-annealer and matrix-multiplication primitive for edge computing

  2025cites this paper
• A rich model for the tramp ship routing and scheduling problem—Solved through column generation

  2025cites this paper
• StructVizor: Interactive Profiling of Semi-Structured Textual Data

  2025cites this paper
• Insights into structural vaccinology harnessed for universal coronavirus vaccine development

  2024cites this paper
• A Statistical Optimization Technique to Inform Statistical Resampling Assessments of Phylogenetic Reconstruction Reliability

  2024cites this paper
• Unique and enriched microbes and their potential “allies and foes” in the human gut microbiomes of ASD patients

  2024cites this paper
• TreeWave: command line tool for alignment-free phylogeny reconstruction based on graphical representation of DNA sequences and genomic signal processing

  2024cites this paper
• k-mer-based approaches to bridging pangenomics and population genetics

  2024cites this paper
• Parallel DNA Sequence Alignment on High-Performance Systems with CUDA and MPI

  2024cites this paper
• HAlign 4: a new strategy for rapidly aligning millions of sequences

  2024cites this paper
• Multiple Function Merging for Code Size Reduction

  2024cites this paper
• MFTrans: A multi-feature transformer network for protein secondary structure prediction.

  2024cites this paper
• Multiple Protein Structure Alignment at Scale with FoldMason

  2024cites this paper
• Metagenome comparison (MC): A new framework for detecting unique/enriched OMUs (operational metagenomic units) derived from whole-genome sequencing reads

  2024cites this paper
• A layout framework for genome-wide multiple sequence alignment graphs

  2024cites this paper
• Species specificity and specificity diversity (SSD) framework: a novel method for detecting the unique and enriched species associated with disease by leveraging the microbiome heterogeneity

  2024cites this paper
• Paralelização da Geração de Consistência em Alinhamentos Múltiplos de Sequências Genéticas

  2024cites this paper
• BetaAlign: a deep learning approach for multiple sequence alignment

  2024cites this paper
• PSSP-MFFNet: A Multifeature Fusion Network for Protein Secondary Structure Prediction

  2024cites this paper
• CGRclust: Chaos Game Representation for twin contrastive clustering of unlabelled DNA sequences

  2024cites this paper
• A Birth-Death-Migration Model for Alignment-Free Phylogeny Estimation using k-mer Frequencies

  2024cites this paper
• Progressive Multiple Alignment of Graphs

  2024cites this paper
• Fast and exact gap-affine partial order alignment with POASTA

  2024cites this paper
• Virome comparison (VC): A novel approach to comparing viromes based on virus species specificity and virome specificity diversity

  2023cites this paper
• Computational Analysis, In silico Functional Annotation, and Expression of Recombinant PE_PGRS Protein Biomarkers Found in Mycobacterium tuberculosis

  2023cites this paper
• Hardness and approximation of multiple sequence alignment with column score

  2023cites this paper
• Evaluating Compression-Based Phylogeny Estimation in the Presence of Incomplete Lineage Sorting

  2023cites this paper
• Playing the System: Can Puzzle Players Teach us How to Solve Hard Problems?

  2023cites this paper
• Dynamic Programming Algorithms for Discovery of Antibiotic Resistance in Microbial Genomes

  2023cites this paper
• When Online Citizen Science meets Teaching: Storyfication of a science discovery game to teach, learn, contribute to genomic research

  2023cites this paper
• Regression Based Accuracy Estimation for Multiple Sequence Alignment

  2023influential citation
• Improved structure-related prediction for insufficient homologous proteins using MSA enhancement and pre-trained language model

  2023cites this paper
• Genetic Algorithm for Guide Tree Optimization

  2023cites this paper
• Enhanced Genetic Method for Optimizing Multiple Sequence Alignment

  2023cites this paper
• CNNPRE: A CNN-Based Protocol Reverse Engineering Method

  2023cites this paper
• Exploring Reinforcement Learning Methods for Multiple Sequence Alignment: A Brief Review

  2023cites this paper
• Automated evaluation of multiple sequence alignment methods to handle third generation sequencing errors

  2023cites this paper
• Player-Guided AI outperforms standard AI in Sequence Alignment Puzzles

  2023cites this paper
• A novel shape-based averaging algorithm for time series

  2023cites this paper
• CGO: G: Multiple Function Merging for Code Size Reduction

  2023cites this paper
• Reconstructing Phylogenies Using Branch-Variable Substitution Models and Unaligned Biomolecular Sequences: A Performance Study and New Resampling Method

  2023cites this paper
• Retrieved Sequence Augmentation for Protein Representation Learning

  2023cites this paper
• On closing the inopportune gap with consistency transformation and iterative refinement

  2023cites this paper
• Generation of Regular Expression from Aligned Sequences of Text Snippets

  2023cites this paper
• Revision 1: parsimony optimization of phylogenetic networks.

  2023cites this paper
• Complementing Solutions for Facility Location Optimization via Video Game Crowdsourcing and Machine Learning Approach

  2023cites this paper
• Much ado about nothing: inapplicable data as insertion–deletion events

  2023cites this paper
• Method of genomes comparative analysis using graph DBMS

  2023cites this paper
• Multiple genome alignment in the telomere-to-telomere assembly era

  2022cites this paper
• ApHMM: Accelerating Profile Hidden Markov Models for Fast and Energy-efficient Genome Analysis

  2022cites this paper
• Harnessing machine translation methods for sequence alignment

  2022cites this paper
• On the role of metaheuristic optimization in bioinformatics

  2022cites this paper
• Physicochemical properties and homology studies of the floral meristem identity gene LFY in nonflowering and flowering plants

  2022cites this paper
• When Citizen Science meets Teaching: A storified citizen science computer game to teach and contribute to genomic data analysis

  2022cites this paper
• Extracting Land Use Change Patterns of Rural Town Settlements with Sequence Alignment Method

  2022cites this paper
• Extracting Formats of Service Messages with Varying Payloads

  2022cites this paper
• Mining metagenomes reveals diverse antibiotic biosynthetic genes in uncultured microbial communities

  2022cites this paper
• A Hybrid Genetic Algorithm using Progressive Alignment and Consistency based Approach for Multiple Sequence Alignments

  2022cites this paper
• Developing new genetic algorithm based on integer programming for multiple sequence alignment

  2022cites this paper
• Optimal Communication Spanning Tree

  2022cites this paper
• Sub-messages extraction for industrial control protocol reverse engineering

  2022cites this paper
• Fast Phylogeny of SARS-CoV-2 by Compression

  2022cites this paper
• Pedometer-free Geomagnetic Fingerprinting with Casual Walking Speed

  2022cites this paper
• Application of the MAHDS Method for Multiple Alignment of Highly Diverged Amino Acid Sequences

  2022cites this paper
• The multiple alignments of very short sequences

  2021cites this paper
• Intuitionistic fuzzy approach improve protein multiple sequence alignment

  2021cites this paper
• DeLUCS: Deep learning for unsupervised clustering of DNA sequences

  2021cites this paper
• Quality of solution of massively parallel MSA based on metaheuristic social behavioral model

  2021cites this paper
• Detection of Highly Divergent Tandem Repeats in the Rice Genome

  2021cites this paper
• A Hybrid Approach using Progressive and Genetic Algorithms for Improvements in Multiple Sequence Alignments

  2021cites this paper
• Deep hierarchical embedding for simultaneous modeling of GPCR proteins in a unified metric space

  2021cites this paper
• Hardness of MSA with Selective Column Scoring

  2021cites this paper
• Rapid alignment updating with Extensiphy

  2021cites this paper
• Efficient Multiple Sequences Alignment Algorithm Generation via Components Assembly Under PAR Framework

  2021cites this paper
• Mapping the proteome with data-driven methods: A cycle of measurement, modeling, hypothesis generation, and engineering

  2021cites this paper
• Research on Components Assembly Platform of Biological Sequences Alignment Algorithm

  2021cites this paper
• Association analysis and identification of unknown bitstream protocols based on composite feature sets

  2021cites this paper
• cognac: rapid generation of concatenated gene alignments for phylogenetic inference from large, bacterial whole genome sequencing datasets

  2021cites this paper
• Multiple Alignment of Promoter Sequences from the Arabidopsis thaliana L. Genome

  2021cites this paper
• Biology and medicine in the landscape of quantum advantages

  2021influential citation
• Fast Whole-Genome Phylogeny by Compression: the COVID-19 case

  2021cites this paper
• An accurate and exact clustering algorithm for next generation sequencing metagenomic sequences

  2021cites this paper
• Harris Hawks Optimizer for Solving Multiple Sequence Alignment

  2021cites this paper
• Accuracy of multiple sequence alignment methods in the reconstruction of transposable element families

  2021cites this paper