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

The footprint sorting problem.

Claudia Fried1, Wim Hordijk, Sonja J Prohaska

  • 1Bioinformatics, Department of Computer Science, University of Leipzig, Germany.

Journal of Chemical Information and Computer Sciences
|March 23, 2004
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

Extension of partial atom-to-atom maps: uniqueness and algorithms.

Algorithms for molecular biology : AMB·2026
Same author

Enumeration of Autocatalytic Subsystems in Large Chemical Reaction Networks.

Journal of chemical theory and computation·2026
Same author

ProQSAR: A modular and reproducible framework for small-data QSAR modeling with fit-and-use models.

Journal of cheminformatics·2026
Same author

SynRXN: An Open Benchmark and Curated Dataset for Computational Reaction Modeling.

Scientific data·2026
Same author

mdxplain: Scalable molecular dynamics analysis with machine learning-based feature selection and modular workflows.

Journal of molecular biology·2026
Same author

From Small Parsimony to Horizontal Gene Transfer: Inferring Horizontal Transfer and Gene Loss for Single-Origin Characters.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same journal

Future Papers.

Journal of chemical information and computer sciences·2016
Same journal

Future Papers.

Journal of chemical information and computer sciences·2016
Same journal

Future Papers.

Journal of chemical information and computer sciences·2016
Same journal

Future Papers.

Journal of chemical information and computer sciences·2016
Same journal

Future Papers.

Journal of chemical information and computer sciences·2016
Same journal

Future Papers.

Journal of chemical information and computer sciences·2016
See all related articles

Sorting conserved DNA sequences called phylogenetic footprints is complex due to their non-collinear nature. This study presents computational methods to order these footprints, revealing evolutionary insights like differing insertion/deletion rates between species.

Area of Science:

  • Bioinformatics
  • Computational Biology
  • Evolutionary Genomics

Background:

  • Phylogenetic footprints are conserved noncoding DNA sequences near genes, crucial for understanding evolutionary relationships.
  • Ordering these footprints along genomes is challenging due to their potential to cross each other (non-collinearity).

Purpose of the Study:

  • To develop and evaluate computational methods for accurately sorting non-collinear phylogenetic footprints across species.
  • To address the computational complexity of footprint ordering by leveraging graph theory and optimization techniques.

Main Methods:

  • The study frames footprint sorting as the Minimum Weight Vertex Feedback Set Problem, an NP-complete problem.
  • Approximation algorithms and general-purpose heuristics were employed to solve the combinatorial optimization problem.

Related Experiment Videos

  • Techniques include transitive closure computation, linear extension of partial orders, and modified multiple sequence alignment for comparison.

    • Main Results:

    • Demonstrated that good approximations for footprint sorting are achievable for relevant datasets.
    • Developed a pipeline for sorting collinear and non-collinear footprints, including insertion of non-collinear elements.
    • Applied the method to compare rat and mouse genomes, identifying a higher insertion/deletion rate in rats.

    Conclusions:

    • The computational approach effectively addresses the challenge of sorting non-collinear phylogenetic footprints.
    • This methodology provides a robust framework for comparative genomics and evolutionary analysis.
    • The findings highlight species-specific differences in genome dynamics, such as insertion/deletion rates.