Modified SIMPSON O(n3) algorithm for the full sibship reconstruction problem.
BACKGROUND
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.


BACKGROUND
Computer code written in Java is available upon request from the first author.


BACKGROUND
Dmitry.Konovalov@jcu.edu.au.
Konovalov
Dmitry A
DA
School of Information Technology, James Cook University Townsville, QLD, Australia. Dmitry.Konovalov@jcu.edu.au
Bajema
Nigel
N
Litow
Bruce
B
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D005819:Genetic Markers / Q000235:genetics*; D005828:Genetics, Population / Q000379:methods*; D006801:Humans; D009716:Numerical Analysis, Computer-Assisted; D010375:Pedigree; D035781:Siblings
D005819:Genetic Markers