Partition-distance via the assignment problem

Konovalov, Dmitry A.;Litow, Bruce;Bajema, Nigel

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.

Journal

Bioinformatics

Publication Name

N/A

Volume

ISBN/ISSN

1367-4811

Edition

N/A

Issue

Pages Count

Location

N/A

Publisher

Oxford University Press

Publisher Url

N/A

Publisher Location

N/A

Publish Date

N/A

Url

N/A

Date

N/A

EISSN

N/A

DOI

10.1093/bioinformatics/bti373