Modified Simpson O(n3) algorithm for the full sibship reconstruction problem
Konovalov, Dmitry, Bajema, Nigel, and Litow, Bruce (2005) Modified Simpson O(n3) algorithm for the full sibship reconstruction problem. Bioinformatics, 21 (20). pp. 3912-3917.
PDF (Published Version)
- Published Version
Restricted to Repository staff only
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(n3) 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(na), where a > 3.
Availability: Computer code written in Java is available upon request from the first author.
|Item Type:||Article (Refereed Research - C1)|
|Date Deposited:||28 Jan 2010 05:48|
|FoR Codes:||08 INFORMATION AND COMPUTING SCIENCES > 0899 Other Information and Computing Sciences > 089999 Information and Computing Sciences not elsewhere classified @ 100%|
|SEO Codes:||89 INFORMATION AND COMMUNICATION SERVICES > 8999 Other Information and Communication Services > 899999 Information and Communication Services not elsewhere classified @ 100%|
|Citation Count from Web of Science||