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: [email protected].

MOTIVATION: Accuracy testing of various pedigree reconstruction methods requires an efficient algorithm for the calculation of distance between a known partition and its reconstruction. The currently used algorithm of Almudevar and Field takes a prohibitively long time for certain partitions and population sizes. RESULTS: We present an algorithm that very efficiently reduces the partition-distance calculation to the classic assignment problem of weighted bipartite graphs that has known polynomial-time solutions. The performance of the algorithm is tested against the Almudevar and Field partition-distance algorithm to verify the significant improvement in speed. AVAILABILITY: Computer code written in java is available upon request from the first author.

An almost uniform $NC^1 $ circuit family for integer division is presented. The circuit size is $O(n^6 / \log (n))$. The circuit design is based on modular representation for integers below $2^n $. In particular, a very efficient technique is introduced for computing “$a < b$?” when a and b in modular representation. This leads to a uniform $NC^1 $ circuit of $O(n^2 )$ size for comparison of integers in modular representation.