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

DOI: 10.1093/bioinformatics/bti373

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 (Research - C1)
ISSN:	1367-4811
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.
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%
Downloads:	Total: 3
	More Statistics

Actions (Repository Staff Only)

Item Control Page