Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Exemplar longest common subsequence.

Paola Bonizzoni1, Gianluca Della Vedova, Riccardo Dondi

  • 1Dipartimento di Informatica, Sistemistica e Communicazione, Universitá degli Studi di Milano-Bicocca, Via Bicocca Degli, Arcimboldi, Milano, Italy. bonizzoni@disco.unimib.it

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|November 3, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

<i>SpecPeptidOMS</i> Directly and Rapidly Aligns Mass Spectra on Whole Proteomes and Identifies Peptides That Are Not Necessarily Tryptic: Implications for Peptidomics.

Journal of proteome research·2025
Same author

Differential quantification of alternative splicing events on spliced pangenome graphs.

PLoS computational biology·2024
Same author

PangeBlocks: customized construction of pangenome graphs via maximal blocks.

BMC bioinformatics·2024
Same author

Diverse somatic Transformer and sex chromosome karyotype pathways regulate gene expression in Drosophila gonad development.

bioRxiv : the preprint server for biology·2024
Same author

Partition Based Algorithms for Rearrangement Distances With Flexible Intergenic Regions.

IEEE transactions on computational biology and bioinformatics·2024
Same author

Data Structures for SMEM-Finding in the PBWT.

International Symposium on String Processing and Information Retrieval : SPIRE ... : proceedings. SPIRE (Symposium)·2024
Same journal

circ2DGNN: circRNA-Disease Association Prediction via Transformer-Based Graph Neural Network.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Hierarchical Hypergraph Learning in Association- Weighted Heterogeneous Network for miRNA- Disease Association Identification.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Discriminative Domain Adaption Network for Simultaneously Removing Batch Effects and Annotating Cell Types in Single-Cell RNA-Seq.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

MLW-BFECF: A Multi-Weighted Dynamic Cascade Forest Based on Bilinear Feature Extraction for Predicting the Stage of Kidney Renal Clear Cell Carcinoma on Multi-Modal Gene Data.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

An End-to-End Knowledge Graph Fused Graph Neural Network for Accurate Protein-Protein Interactions Prediction.

IEEE/ACM transactions on computational biology and bioinformatics·2024
Same journal

Generative Biomedical Event Extraction With Constrained Decoding Strategy.

IEEE/ACM transactions on computational biology and bioinformatics·2024
See all related articles

This study explores the complexity of the Exemplar Longest Common Subsequence (ELCS) problem. While generally NP-hard, efficient algorithms are presented for specific cases with limited mandatory symbols.

Area of Science:

  • Theoretical Computer Science
  • Computational Biology
  • Bioinformatics

Background:

  • The Longest Common Subsequence (LCS) problem is fundamental in sequence analysis.
  • The Exemplar Longest Common Subsequence (ELCS) problem generalizes LCS by incorporating mandatory and optional symbols.
  • Understanding the computational complexity of ELCS is crucial for its practical application.

Purpose of the Study:

  • To investigate the computational and approximation complexity of the ELCS problem.
  • To analyze the hardness of ELCS for instances with two sequences.
  • To develop efficient algorithms for specific ELCS problem variants.

Main Methods:

  • Analysis of approximation algorithms for ELCS.
  • NP-hardness and APX-hardness proofs for ELCS variants.

Related Experiment Videos

  • Design of efficient algorithms for restricted ELCS instances.
  • Development of fixed-parameter tractable algorithms for ELCS.

    • Main Results:

    • The ELCS problem is shown to be APX-hard even for two sequences.
    • Determining the existence of a feasible ELCS solution for two sequences is NP-hard.
    • An efficient algorithm is presented for ELCS with limited occurrences of mandatory symbols.
    • Two fixed-parameter algorithms are developed based on the number of mandatory symbols.

    Conclusions:

    • The ELCS problem presents significant computational challenges, particularly regarding approximation.
    • Efficient algorithmic solutions exist for specific, constrained instances of the ELCS problem.
    • Fixed-parameter approaches offer a viable path for solving ELCS with a limited number of mandatory symbols.