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 Concept Videos

Mismatch Repair01:36

Mismatch Repair

43.5K
Overview
43.5K
Mismatch Repair01:20

Mismatch Repair

6.4K
Organisms are capable of detecting and fixing nucleotide mismatches that occur during DNA replication. This sophisticated process requires identifying the new strand and replacing the erroneous bases with correct nucleotides. Mismatch repair is coordinated by many proteins in both prokaryotes and eukaryotes.
The Mutator Protein Family Plays a Key Role in DNA Mismatch Repair
The human genome has more than 3 billion base pairs of DNA per cell. Prior to cell division, that vast amount of genetic...
6.4K
Overview of DNA Repair02:25

Overview of DNA Repair

33.5K
In order to be passed through generations, genomic DNA must be undamaged and error-free. However, every day, DNA in a cell undergoes several thousand to a million damaging events by natural causes and external factors. Ionizing radiation such as UV rays, free radicals produced during cellular respiration, and hydrolytic damage from metabolic reactions can alter the structure of DNA. Damages caused include single-base alteration, base dimerization, chain breaks, and cross-linkage.
Chemically...
33.5K
Base Excision Repair01:54

Base Excision Repair

26.1K
One of the common DNA damages is the chemical alteration of single bases by alkylation, oxidation, or deamination. The altered bases cause mispairing and strand breakage during replication. This type of damage causes minimal change to the DNA double helix structure and can be repaired by the base excision repair (BER) pathways. BER corrects damaged DNA sequences by removing the damaged base and restoring the original base sequence using the complementary strand as a template.
The first step of...
26.1K
Nucleotide Excision Repair01:08

Nucleotide Excision Repair

40.6K
Overview
40.6K
Long-patch Base Excision Repair01:02

Long-patch Base Excision Repair

7.9K
Since the discovery of the two BER pathways, there has been a debate about how a cell chooses one pathway over the other and the factors determining this selection. Numerous in vitro experiments have pointed out multiple determinants for the sub-pathway selection. These are:
7.9K

You might also read

Related Articles

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

Sort by
Same author

Non-adiabatic origin of roaming OH dynamics in the formic acid dimer dication.

Physical chemistry chemical physics : PCCP·2026
Same author

A Double Machine Learning Approach for Combining Experimental and Observational Studies.

Observational studies·2026
Same author

Ultrafast and Ultraslow Proton-Transfer Dynamics Induced by Formic Acid Dimer Ionization.

The journal of physical chemistry. A·2025
Same author

Photochemical pathways in astronomical ices: A computational study of singlet oxygen reactions with hydrocarbons.

The Journal of chemical physics·2025
Same author

Symmetry-breaking dynamics of a photoionized carbon dioxide dimer.

Nature communications·2024
Same author

Time-resolving the ultrafast H<sub>2</sub> roaming chemistry and H<sub>3</sub><sup>+</sup> formation using extreme-ultraviolet pulses.

Communications chemistry·2023
Same journal

Subspace exploration: Bounds on Projected Frequency Estimation.

Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems·2021
Same journal

Data Citation: a Computational Challenge.

Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems·2017
See all related articles

Related Experiment Video

Updated: Jan 23, 2026

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

7.7K

Computing Optimal Repairs for Functional Dependencies.

Ester Livshits1, Benny Kimelfeld1, Sudeepa Roy2

  • 1Technion, Haifa 32000, Israel.

Proceedings of the ... ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
|June 18, 2019
PubMed
Summary
This summary is machine-generated.

This study explores database repair complexity using Functional Dependencies (FDs). We introduce a dichotomy for optimal repairs, showing some problems are efficiently solvable while others are NP-hard.

More Related Videos

Computational Reconstruction of Pancreatic Islets as a Tool for Structural and Functional Analysis
07:58

Computational Reconstruction of Pancreatic Islets as a Tool for Structural and Functional Analysis

Published on: March 9, 2022

1.9K
Using High Resolution Computed Tomography to Visualize the Three Dimensional Structure and Function of Plant Vasculature
11:49

Using High Resolution Computed Tomography to Visualize the Three Dimensional Structure and Function of Plant Vasculature

Published on: April 5, 2013

21.6K

Related Experiment Videos

Last Updated: Jan 23, 2026

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues
07:08

Optimization of Synthetic Proteins: Identification of Interpositional Dependencies Indicating Structurally and/or Functionally Linked Residues

Published on: July 14, 2015

7.7K
Computational Reconstruction of Pancreatic Islets as a Tool for Structural and Functional Analysis
07:58

Computational Reconstruction of Pancreatic Islets as a Tool for Structural and Functional Analysis

Published on: March 9, 2022

1.9K
Using High Resolution Computed Tomography to Visualize the Three Dimensional Structure and Function of Plant Vasculature
11:49

Using High Resolution Computed Tomography to Visualize the Three Dimensional Structure and Function of Plant Vasculature

Published on: April 5, 2013

21.6K

Area of Science:

  • Database Theory
  • Computational Complexity
  • Data Management

Background:

  • Database inconsistency arises from violations of integrity constraints.
  • Functional Dependencies (FDs) are crucial constraints in relational databases.
  • Efficiently repairing inconsistent databases is a significant challenge.

Purpose of the Study:

  • To analyze the computational complexity of optimal database repairs under Functional Dependencies (FDs).
  • To investigate two repair types: optimal subset repair (S-repair) via tuple deletions and optimal update repair (U-repair) via value updates.
  • To establish a complexity dichotomy for optimal S-repairs and extend analysis to U-repairs.

Main Methods:

  • Development of a polynomial-time algorithm for optimal S-repair.
  • Complexity analysis using NP-hardness and APX-completeness proofs.
  • General analytical techniques for U-repair complexity, leveraging S-repair dichotomy.
  • Connection to existing dichotomies for "most probable database" problems.

Main Results:

  • A dichotomy is established for optimal S-repair complexity: polynomial-time solvable for some FD sets, NP-hard and APX-complete for others.
  • The polynomial-time algorithm for S-repair can handle weighted and duplicate tuples.
  • General techniques for U-repair complexity are presented, building upon the S-repair findings.
  • The study settles an open problem regarding the complexity of finding a "most probable database" for general FDs.

Conclusions:

  • The complexity of optimal database repair under FDs exhibits a clear dichotomy.
  • The findings provide a comprehensive understanding of the computational landscape for database repairs.
  • This work generalizes previous results and resolves open questions in database theory.