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

Reconstruction of a string from substring precedence data

A R Rubinov1, M S Gelfand

  • 1Institute of Protein Research, Russian Academy of Sciences, Puschchino, Moscow region, Russia.

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|January 1, 1995
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

ProAD - A database of rotary ion-translocating ATPases in prokaryotic genomes.

Frontiers in molecular biosciences·2025
Same author

Towards practical applications in quantum computational biology.

Nature computational science·2024
Same author

Re: 'Cefazolin versus anti-staphylococcal penicillins for the treatment of patients with Staphylococcus aureus bacteremia' by Weis et al.

Clinical microbiology and infection : the official publication of the European Society of Clinical Microbiology and Infectious Diseases·2019
Same author

Serum-derived bovine immunoglobulin/protein isolate should be considered in patients with HIV gut barrier dysfunction.

Infection·2015
Same author

Posaconazole as successful treatment for fungemia due to Cryptococcus albidus in a liver transplant recipient.

QJM : monthly journal of the Association of Physicians·2012
Same author

Regulation and evolution of malonate and propionate catabolism in proteobacteria.

Journal of bacteriology·2012

This study addresses reconstructing symbol strings from substring data, crucial for nucleic acid sequencing. Efficient algorithms are presented to determine solution existence, uniqueness, and construct the sequence.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Graph Theory

Background:

  • Nucleic acid sequencing by nested strand hybridization generates data on fixed-length substrings.
  • Reconstructing the original symbol string from this data is a complex computational challenge.

Purpose of the Study:

  • To reformulate the nucleic acid sequencing reconstruction problem using graph theory.
  • To develop efficient algorithms for analyzing the solution space of such reconstruction problems.

Main Methods:

  • Graph-theoretical reformulation of the string reconstruction problem.
  • Development of polynomial-time algorithms to analyze solution existence, uniqueness, and finiteness.
  • Algorithmic construction of solutions when they exist.

Related Experiment Videos

Main Results:

  • The problem is effectively modeled using graph theory.
  • Algorithms are provided to efficiently determine if a unique solution exists or if the solution set is finite.
  • Methods for constructing the reconstructed symbol string are presented.

Conclusions:

  • The graph-theoretical approach provides a robust framework for solving string reconstruction problems in sequencing.
  • The developed polynomial-time algorithms offer efficient computational solutions for analyzing and constructing nucleic acid sequences.