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

Using traveling salesman problem algorithms for evolutionary tree construction.

C Korostensky1, G H Gonnet

  • 1Institute for Scientific Computing, 8092 ETH Zurich, Switzerland. chantal.roth@nobilitas.com

Bioinformatics (Oxford, England)
|October 20, 2000
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

An analysis of the helix-to-strand transition between peptides with identical sequence.

Proteins·2000
Same author

Evaluation measures of multiple sequence alignments.

Journal of computational biology : a journal of computational molecular cell biology·2000
Same author

Darwin v. 2.0: an interpreted computer language for the biosciences.

Bioinformatics (Oxford, England)·2000
Same author

An algorithm for the identification of proteins using peptides with ragged N- or C-termini generated by sequential endo- and exopeptidase digestions.

Electrophoresis·1998
Same author

A combinatorial distance-constraint approach to predicting protein tertiary models from known secondary structure.

Folding & design·1998
Same author

A genetic system based on split-ubiquitin for the analysis of interactions between membrane proteins in vivo.

Proceedings of the National Academy of Sciences of the United States of America·1998
Same journal

Biomedical Concept Recognition with Error-aware Negative-enhanced Ranking Framework.

Bioinformatics (Oxford, England)·2026
Same journal

TEDLH: Domain HMMs for sensitive detection of remote homologues.

Bioinformatics (Oxford, England)·2026
Same journal

PLNFGL: Joint Estimation of Multi-Condition Gene Networks from Single-cell RNA-seq Data.

Bioinformatics (Oxford, England)·2026
Same journal

MCFST: Spatial domain identification method based on multi-view graph convolutional network and graph fusion network.

Bioinformatics (Oxford, England)·2026
Same journal

SpaBiT: Enhancing Spatial Transcriptomics Resolution via Bidirectional Attention Transformers.

Bioinformatics (Oxford, England)·2026
Same journal

EDEL: Enhancing Dense Retrievers for Curation of Biomedical Knowledge Bases.

Bioinformatics (Oxford, England)·2026
See all related articles

We introduce a novel computational biology method to construct evolutionary trees by reducing the problem to the Traveling Salesman Problem (TSP). This approach efficiently finds the minimum evolutionary score and tree topology for sequence data.

Area of Science:

  • Computational Biology
  • Phylogenetics
  • Bioinformatics

Background:

  • Constructing accurate evolutionary trees is a complex challenge in computational biology.
  • Existing methods face limitations in efficiency and accuracy for large datasets.

Purpose of the Study:

  • To develop a novel, efficient method for constructing evolutionary trees with a minimum evolutionary score.
  • To leverage the Traveling Salesman Problem (TSP) for tree topology determination.

Main Methods:

  • The study reduces the evolutionary tree construction problem to the Traveling Salesman Problem (TSP).
  • Pairwise sequence distances are used as input for the TSP algorithm.
  • A dynamic programming approach is employed for datasets with significant error margins.

Related Experiment Videos

Main Results:

  • The method successfully reduces the search space of possible trees.
  • It guarantees accurate reconstruction under specific error conditions.
  • The approach yields the minimum evolutionary score and optimal tree topology.

Conclusions:

  • This TSP-based method offers an efficient and accurate solution for evolutionary tree construction.
  • The technique is adaptable to various scoring functions, including parsimony.
  • It provides a robust framework for phylogenetic analysis, particularly with large sequence datasets.