title: Partition-distance via the assignment problem.
abstract: 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.
authors.affiliation: School of Information Technology, James Cook University, Townsville, QLD 4811, Australia. dmitry.konovalov@jcu.edu.au
authors.forename: Dmitry A
authors.initials: DA
authors.lastname: Konovalov
authors.forename: Bruce
authors.initials: B
authors.lastname: Litow
authors.forename: Nigel
authors.initials: N
authors.lastname: Bajema
mesh_terms: 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