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

Modified SIMPSON O(n3) algorithm for the full sibship reconstruction problem.

Dmitry A Konovalov1, Nigel Bajema, Bruce Litow

  • 1School of Information Technology, James Cook University Townsville, QLD, Australia. Dmitry.Konovalov@jcu.edu.au

Bioinformatics (Oxford, England)
|August 25, 2005
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

Canapes in the canopy: Canopy macroalgae are dining hotspots for small and juvenile fishes at Orpheus Island, Great Barrier Reef.

Marine environmental research·2025
Same author

Accelerating segmentation of fossil CT scans through Deep Learning.

Scientific reports·2024
Same author

The effect of neuter status on longevity in the Rottweiler dog.

Scientific reports·2023
Same author

Field-based adipose tissue quantification in sea turtles using bioelectrical impedance spectroscopy validated with CT scans and deep learning.

Ecology and evolution·2022
Same author

Environmental conditions constrain nursery habitat value in Australian sub-tropical estuaries.

Marine environmental research·2022
Same author

Age- and sex-dependent variation in relatedness corresponds to reproductive skew, territory inheritance, and workload in cooperatively breeding cichlids.

Evolution; international journal of organic evolution·2021

A new modified SIMPSON (MS) algorithm improves full sibship reconstruction (FSR) efficiency. This computational biology tool runs in O(n(3)) time, offering significant speedups over the original SIMPSON algorithm for DNA marker data analysis.

Area of Science:

  • Computational Biology
  • Bioinformatics
  • Genetics

Background:

  • Full sibship reconstruction (FSR) from DNA marker data is a complex computational problem.
  • A heuristic algorithm using Mendelian exclusion and Simpson index was previously applied to FSR.
  • The original SIMPSON algorithm's computational complexity was unknown, limiting its practical application.

Purpose of the Study:

  • To address the limitations of the original SIMPSON algorithm for full sibship reconstruction.
  • To develop a modified SIMPSON (MS) algorithm with a defined and improved complexity.
  • To evaluate the accuracy and efficiency of the MS algorithm compared to the original SIMPSON algorithm.

Main Methods:

  • Development of a modified SIMPSON (MS) algorithm.

Related Experiment Videos

  • Analysis of computational complexity, theoretically determining it to be O(n(3)).
  • Testing the MS algorithm's performance on simulated diploid population samples.

    • Main Results:

    • The modified SIMPSON (MS) algorithm exhibits a time complexity of O(n(3)).
    • The MS algorithm achieves comparable or superior accuracy to the original SIMPSON algorithm.
    • Efficiency improvements of up to 100 times were observed for the MS algorithm in simulations.
    • Theoretical analysis confirmed the original SIMPSON algorithm runs in non-polynomial time (O(n(a)), a > 3).

    Conclusions:

    • The modified SIMPSON (MS) algorithm provides a computationally tractable and efficient solution for full sibship reconstruction.
    • The MS algorithm overcomes the complexity limitations of the original SIMPSON algorithm, expanding its applicability.
    • This advancement offers a more practical tool for analyzing DNA marker data in computational biology.