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.

[img] PDF (Published Version) - Published Version
Restricted to Repository staff only

View at Publisher Website: http://dx.doi.org/10.1093/bioinformatics...

Abstract

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 ID: 487
Item Type: Article (Refereed Research - C1)
Keywords: population biology, partition distance, assignment problem, polynomial time
Additional Information:

Copyright © 2004 Oxford University Press. The published version of this article can be accessed via Oxford Journals. Use hypertext links above.

ISSN: 1367-4811
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 Web of Science 15
Downloads: Total: 3
More Statistics

Actions (Repository Staff Only)

Item Control Page Item Control Page