Related Experiment Video
Updated: Aug 16, 2026

A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles
Published on: July 11, 2025
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
Motivation:
The problem of reconstructing full sibling groups from DNA marker data remains a significant challenge for computational biology. A recently published heuristic algorithm based on Mendelian exclusion rules and the Simpson index was successfully applied to the full sibship reconstruction (FSR) problem. However, the so-called SIMPSON algorithm has an unknown complexity measure, questioning its applicability range.
Results:
We present a modified version of the SIMPSON (MS) algorithm that behaves as O(n(3)) and achieves the same or better accuracy when compared with the original algorithm. Performance of the MS algorithm was tested on a variety of simulated diploid population samples to verify its complexity measure and the significant improvement in efficiency (e.g. 100 times faster than SIMPSON in some cases). It has been shown that, in theory, the SIMPSON algorithm runs in non-polynomial time, significantly limiting its usefulness. It has been also verified via simulation experiments that SIMPSON could run in O(n(a)), where a > 3.
Availability:
Computer code written in Java is available upon request from the first author.
Contact:
Dmitry.Konovalov@jcu.edu.au.
More Related Videos
08:03Midface Hypoplasia and Cranial Base Morphology in Syndromic Craniosynostosis: A Comparative Analysis Study Using a Predictive Regression Model
Published on: November 4, 2025
08:03Heuristic Mining of Hierarchical Genotypes and Accessory Genome Loci in Bacterial Populations
Published on: December 7, 2021
Related Concept Videos
Simpson's Rule II
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
One-Compartment Open Model: Wagner-Nelson and Loo Riegelman Method for ka Estimation
On...
Multimachine Stability
In analyzing the system, the nodal equations represent the relationship between bus voltages, machine voltages, and machine currents. The nodal equation is given by:
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
Evolutionary Relationships through Genome Comparisons