title: Modified SIMPSON O(n3) algorithm for the full sibship reconstruction problem.
abstract: 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.
authors.affiliation: School of Information Technology, James Cook University Townsville, QLD, Australia. Dmitry.Konovalov@jcu.edu.au
authors.forename: Dmitry A
authors.initials: DA
authors.lastname: Konovalov
authors.forename: Nigel
authors.initials: N
authors.lastname: Bajema
authors.forename: Bruce
authors.initials: B
authors.lastname: Litow
mesh_terms: 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
chemical_list: D005819:Genetic Markers