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

Breakpoint medians and breakpoint phylogenies: a fixed-parameter approach.

Jens Gramm1, Rolf Niedermeier

  • 1Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Federic Republic of Germany.

Bioinformatics (Oxford, England)
|October 19, 2002
PubMed
Summary

This study introduces an exact, fixed-parameter algorithm for the breakpoint median problem in phylogenetic analysis. The new method efficiently computes evolutionary trees, offering competitive results for genome rearrangement studies.

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

Combining Clickstream Analyses and Graph-Modeled Data Clustering for Identifying Common Response Processes.

Psychometrika·2021
Same author

Stable roommates with narcissistic, single-peaked, and single-crossing preferences.

Autonomous agents and multi-agent systems·2020
Same author

Parameterized Algorithmics for Finding Exact Solutions of NP-Hard Biological Problems.

Methods in molecular biology (Clifton, N.J.)·2016
Same author

Partitioning Biological Networks into Highly Connected Clusters with Maximum Edge Coverage.

IEEE/ACM transactions on computational biology and bioinformatics·2015
Same author

Exploiting bounded signal flow for graph orientation based on cause-effect pairs.

Algorithms for molecular biology : AMB·2011
Same author

Parameterized algorithmics for finding connected motifs in biological networks.

IEEE/ACM transactions on computational biology and bioinformatics·2011

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Genomics

Background:

  • Breakpoint distance is a popular measure in phylogenetic studies for related species.
  • The breakpoint median problem is central to genome rearrangement analysis but is NP-complete.
  • Existing algorithms for three species include approximation and heuristic methods.

Purpose of the Study:

  • To develop an exact, fixed-parameter algorithm for the breakpoint median problem.
  • To provide provable performance bounds for the algorithm.
  • To demonstrate the practical utility of the algorithm in breakpoint phylogeny.

Main Methods:

  • Developed an exact, fixed-parameter algorithm for computing the breakpoint median.
  • Analyzed the algorithm's time complexity: O((2.15)^d * n) for d breakpoints and n elements.

Related Experiment Videos

  • Combined the algorithm with a novel tree construction heuristic for phylogenetic analysis.

    • Main Results:

    • The algorithm computes breakpoint medians for three signed orderings with at most d breakpoints in O((2.15)^d * n) time.
    • Experimental studies confirmed the algorithm's practical usefulness.
    • The new approach to breakpoint phylogeny yielded competitive evolutionary trees.

    Conclusions:

    • The presented fixed-parameter algorithm offers an efficient and exact solution for the breakpoint median problem.
    • This work advances breakpoint phylogeny by providing a practical and competitive method for constructing evolutionary trees.
    • The algorithm's performance bounds and experimental validation highlight its significance in genome rearrangement studies.