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

Ortholog clustering on a multipartite graph.

Akshay Vashist1, Casimir A Kulikowski, Ilya Muchnik

  • 1Department of Computer Science, Rutgers-The State University of New Jersey, Piscataway 08854, USA. vashisht@cs.rutgers.edu

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|February 6, 2007
PubMed
Summary

We developed a new clustering algorithm to automatically identify groups of orthologous genes across multiple genomes. This method accurately identifies gene clusters by analyzing sequence similarities and genome relationships, improving upon existing methods.

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

50 Years of Achievements and Persistent Challenges for Biomedical and Health Informatics and John Mantas' Educational and Nursing Informatics Contributions.

Studies in health technology and informatics·2022
Same author

Ethics in the History of Medical Informatics for Decision-Making: Early Challenges to Digital Health Goals.

Yearbook of medical informatics·2022
Same author

A scientific mind embraces medicine: Donald Lindberg's education and early career.

Information services & use·2022
Same author

A Scientific Mind Embraces Medicine: Donald Lindberg's Education and Early Career.

Studies in health technology and informatics·2022
Same author

Increasing Efficiency and Cost-Effectiveness by Automating the Authoring of the Development Safety Update Report.

Pharmaceutical medicine·2021
Same author

Pandemics: Historically Slow "Learning Curve" Leading to Biomedical Informatics and Vaccine Breakthroughs.

Yearbook of medical informatics·2021

Area of Science:

  • Genomics
  • Bioinformatics
  • Computational Biology

Background:

  • Identifying orthologous genes is crucial for comparative genomics and understanding gene function across species.
  • Existing methods for ortholog clustering can be computationally intensive and may not scale well with large genomic datasets.

Purpose of the Study:

  • To present a novel, efficient algorithm for the automatic extraction of orthologous gene clusters from large-scale genomic data.
  • To formulate ortholog clustering as a combinatorial optimization problem solvable with a weighted multipartite graph approach.

Main Methods:

  • A new clustering algorithm is introduced, operating on a weighted multipartite graph to group orthologous genes.
  • A scoring system evaluates orthologous relationships based on gene sequence similarities and phylogenetic distances between genomes.

Related Experiment Videos

  • The algorithm's runtime complexity is O(|E| + |V| log |V|), improving to O(|E| + |V|) with score discretization.

    • Main Results:

    • The method was successfully applied to seven complete eukaryote genomes, mirroring the construction of the manually curated Kyoto Encyclopedia of Genes and Genomes (KEGG) Orthology (KO) database.
    • A comparison with manually curated ortholog clusters demonstrated a strong correlation between the algorithm's output and existing, validated clusters.

    Conclusions:

    • The proposed method provides an efficient and accurate approach for automated ortholog clustering in large-scale genomic analyses.
    • This algorithm offers a scalable solution for identifying orthologous genes, facilitating comparative genomics and functional annotation across diverse species.