Partition-distance via the assignment problem.
BACKGROUND
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.


BACKGROUND
Computer code written in java is available upon request from the first author.
Konovalov
Dmitry A
DA
School of Information Technology, James Cook University, Townsville, QLD 4811, Australia. dmitry.konovalov@jcu.edu.au
Litow
Bruce
B
Bajema
Nigel
N
D000465:Algorithms; D002874:Chromosome Mapping / Q000379:methods*; D003198:Computer Simulation; D019143:Evolution, Molecular; D008957:Models, Genetic; D010375:Pedigree; D040641:Quantitative Trait Loci / Q000235:genetics*; D017422:Sequence Analysis, DNA / Q000379:methods*; D012984:Software