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

Positional sequencing by hybridization

S Hannenhalli1, W Feldman, H F Lewis

  • 1Department of Computer Science and Engineering, Pennsylvania State University, University Park 16802, USA.

Computer Applications in the Biosciences : CABIOS
|February 1, 1996
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

Ammoniated phyllosilicates with a likely outer Solar System origin on (1) Ceres.

Nature·2015
Same author

Sevoflurane 2000 Drager Vaporiser 'locked on' during maintenance of anaesthesia.

Anaesthesia and intensive care·2015
Same author

Medical Management of Recurrent ENT Problems in Childhood.

Canadian family physician Medecin de famille canadien·2011
Same author

Immunization and the year of the child: an achievable goal.

Canadian family physician Medecin de famille canadien·2011
Same author

[Not Available].

Canadian family physician Medecin de famille canadien·2011
Same author

How many well baby visits? A randomized trial in progress.

Canadian family physician Medecin de famille canadien·2011
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

Positional sequencing by hybridization (PSBH) improves DNA fragment reconstruction. While the general problem is NP-complete, polynomial algorithms exist for bounded errors and O(log n) errors, enhancing PSBH

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Genomics

Background:

  • Sequencing by hybridization (SBH) offers an alternative to traditional DNA sequencing.
  • Current SBH methods have limited resolving power, reconstructing only short DNA fragments (approx. 200 bp).
  • Positional sequencing by hybridization (PSBH) aims to enhance SBH's resolving power by incorporating positional information of sequence elements.

Purpose of the Study:

  • To investigate the computational complexity of the positional Eulerian path problem, which is central to PSBH.
  • To develop efficient algorithms for PSBH, particularly under conditions of bounded or limited positional error.
  • To analyze the resolving power of PSBH with varying degrees of positional measurement error.

Main Methods:

  • Formulated the positional Eulerian path problem based on PSBH principles.

Related Experiment Videos

  • Utilized graph theory and computational complexity analysis to determine problem hardness.
  • Developed polynomial-time algorithms for specific PSBH scenarios, including bounded positional error.
  • Analyzed algorithm performance with different error models (e.g., O(log n) and O(n) error).

    • Main Results:

    • The general positional Eulerian path problem is NP-complete, even for graphs with maximum degree 2.
    • Polynomial-time algorithms were developed for the bounded PSBH problem, corresponding to accurate positional measurements.
    • Efficient algorithms are feasible when positional errors are within O(log n) for DNA fragments of length n.
    • The study provides estimates for PSBH resolving power under more realistic O(n) error conditions.

    Conclusions:

    • PSBH presents a viable strategy for improving DNA sequencing resolution compared to traditional SBH.
    • Computational challenges exist, but efficient solutions are achievable for practical PSBH implementations with bounded or logarithmic errors.
    • Further research is needed to fully characterize PSBH performance with significant positional measurement errors.