Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Search research articles

Related Experiment Videos

Parameterized complexity analysis in computational biology

H L Bodlaender¹, R G Downey, M R Fellows

¹Computer Science Department, Utrecht University, The Netherlands.

Computer Applications in the Biosciences : CABIOS

|February 1, 1995

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

A metagenomic-based study of two sites from the Barbadian reef system.

Coral reefs (Online)·2023

Same author

In Reply.

Anaesthesia and intensive care·2017

Same author

Erratum to: Detecting gene signature activation in breast cancer in an absolute, single-patient manner.

Breast cancer research : BCR·2017

Same author

Detecting gene signature activation in breast cancer in an absolute, single-patient manner.

Breast cancer research : BCR·2017

Same author

Welfare of anaesthesia trainees survey.

Anaesthesia and intensive care·2017

Same author

Predicting the subcellular localization of viral proteins within a mammalian host cell.

Virology journal·2006

Same journal

DCA: an efficient implementation of the divide-and-conquer approach to simultaneous multiple sequence alignment.

Computer applications in the biosciences : CABIOS·1998

Same journal

Two applications to facilitate the viewing of database search result files on the Macintosh.

Computer applications in the biosciences : CABIOS·1998

Same journal

BioWish: a molecular biology command extension to Tcl/Tk.

Computer applications in the biosciences : CABIOS·1998

Same journal

The Sequence Alerting Server--a new WEB server.

Computer applications in the biosciences : CABIOS·1998

Same journal

A software tool for the analysis of mass spectrometric disulfide mapping experiments.

Computer applications in the biosciences : CABIOS·1998

Same journal

SAMBA: hardware accelerator for biological sequence comparison.

Computer applications in the biosciences : CABIOS·1998

See all related articles

Parameterized computational complexity offers a better approach than NP-completeness for intractable problems in computational biology. This study shows the Longest Common Subsequence problem is W[t]-hard, impacting sequence alignment and consensus discovery.

Area of Science:

Computational Biology
Theoretical Computer Science

Background:

Many computational biology problems have parameters with small, critical value ranges, leading to apparent intractability.
NP-completeness may not be the most effective framework for analyzing these problems.

Purpose of the Study:

To advocate for parameterized computational complexity as a more suitable framework for analyzing intractable problems in computational biology.
To present a new complexity result for the Longest Common Subsequence (LCS) problem.

Main Methods:

Surveying the framework of parameterized computational complexity.
Analyzing the complexity of the LCS problem when parameterized by the number of strings and alphabet size.

Main Results:

Related Experiment Videos

The Longest Common Subsequence problem is demonstrated to be hard for W[t] for all t, under parameterization by the number of strings and alphabet size.

This finding establishes lower bounds for sequence alignment and consensus discovery.

Conclusions:

Parameterized complexity is a crucial tool for understanding computational biology problems with small parameter values.
Further research into open problems in this area is warranted.