Related Experiment Video
Updated: Mar 15, 2026
08:35
An Operant Intra-/Extra-dimensional Set-shift Task for Mice
Published on: January 22, 2016
12.9K
Cautionary Tales of Inapproximability.
David Budden1,2, Mitchell Jones1,3
11 Google, Inc. , Pyrmont, Australia .
Summary
Computational biology leverages computer science theory to analyze biological data. This study explores theoretical limits of algorithms in sequence assembly and alignment, offering insights for practical performance improvements and future innovation.
Area of Science:
- Computational Biology
- Theoretical Computer Science
- Bioinformatics
Background:
- Biological data analysis often employs computational methods, drawing from computer science.
- Limited focus exists on theoretical performance bounds for practical algorithms in computational biology.
- Theoretical studies may overgeneralize findings to biological systems.
Purpose of the Study:
- To provide a fresh perspective on NP-hardness and inapproximability in computational biology.
- To use sequence assembly and alignment algorithms as examples to illustrate theoretical concepts.
- To bridge the gap between theoretical computer science and practical bioinformatics applications.
Main Methods:
- Analysis of NP-hardness and inapproximability concepts within computational biology.
- Illustrative examples using popular sequence assembly algorithms.
- Illustrative examples using popular sequence alignment (mapping) algorithms.
Main Results:
- Computer science theory can significantly enhance practical algorithm performance in bioinformatics.
- Theoretical analysis highlights areas for future innovation in biological data processing.
- Discussion of caveats where heuristic performance may exceed theoretical bounds.
Conclusions:
- Understanding theoretical limits is crucial for advancing computational biology.
- Sequence assembly and alignment serve as key examples for applying theoretical computer science.
- Further research is needed to reconcile theoretical bounds with observed heuristic performance.
Related Concept Videos
01:30The Squeeze Theorem
406
Certain mathematical functions exhibit unpredictable or highly variable behavior near specific input values, making direct evaluation of their limits challenging. This complexity may arise from rapid oscillations or irregular patterns that obscure the function’s trend. In such cases, the Squeeze Theorem offers a reliable method for determining limits.According to the Squeeze Theorem, if a function is confined between two other functions near a particular point, and both outer functions...
406
01:08The Availability Heuristic
7.2K
A heuristic is a general problem-solving framework (Tversky & Kahneman, 1974). You can think of these as mental shortcuts that are used to solve problems. Different types of heuristics are used in different types of situations, and the impulse to use a heuristic occurs when one of five conditions is met (Pratkanis, 1989):
7.2K
01:12Theorems of Pappus and Guldinus: Problem Solving
1.1K
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
1.1K
01:14Avoidance Learning and Learned Helplessness
3.1K
Avoidance learning and learned helplessness are critical concepts in understanding behavioral responses to negative stimuli.
Avoidance learning occurs when an organism learns that a specific behavior can prevent an unpleasant outcome. For example, a student who receives a bad grade may start studying harder to avoid future poor grades. This behavior persists even when the negative outcome is no longer present. Avoidance learning is powerful because it maintains behavior in the absence of the...
Avoidance learning occurs when an organism learns that a specific behavior can prevent an unpleasant outcome. For example, a student who receives a bad grade may start studying harder to avoid future poor grades. This behavior persists even when the negative outcome is no longer present. Avoidance learning is powerful because it maintains behavior in the absence of the...
3.1K
01:12Hindsight Biases
4.5K
Hindsight bias leads you to believe that the event you just experienced was predictable, even though it really wasn’t. In other words, you knew all along that things would turn out the way they did. Can you relate this to the phrase "Hindsight is 20/20" now?
4.5K
01:24Limits at Infinity
391
The function that decreases as the input becomes very large provides a clear example of how mathematical functions can behave at extreme values. When the input increases continuously, the output becomes smaller and smaller, getting closer to a particular fixed value. Although the output never actually reaches this value, it moves nearer to it without limit. This behavior is a fundamental concept in understanding how functions behave as the input grows indefinitely. The graphical representation...
391