Partition-distance via the assignment problem
Konovalov, Dmitry A., Litow, Bruce, and Bajema, Nigel (2005) Partition-distance via the assignment problem. Bioinformatics, 21 (10). pp. 2463-2468.
PDF (Published Version)
- Published Version
Restricted to Repository staff only
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.
|Item Type:||Article (Refereed Research - C1)|
|Keywords:||population biology, partition distance, assignment problem, polynomial time|
Copyright © 2004 Oxford University Press. The published version of this article can be accessed via Oxford Journals. Use hypertext links above.
|Date Deposited:||03 Nov 2006|
|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||