Published in

BioMed Central, BMC Bioinformatics, S1(10), 2009

DOI: 10.1186/1471-2105-10-s1-s61

Links

Tools

Export citation

Search in Google Scholar

On optimal comparability editing with applications to molecular diagnostics

Journal article published in 2009 by Sebastian Böcker ORCID, Sebastian Briesemeister, Gunnar W. Klau
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Upload
Green circle
Postprint: archiving allowed
Upload
Green circle
Published version: archiving allowed
Upload
Policy details
Data provided by SHERPA/RoMEO

Abstract

Abstract Background The C OMPARABILITY E DITING problem appears in the context of hierarchical disease classification based on noisy data. We are given a directed graph G representing hierarchical relationships between patient subgroups. The task is to identify the minimum number of edge insertions or deletions to transform G into a transitive graph, that is, if edges ( u , v ) and ( v , w ) are present then edge ( u , w ) must be present, too. Results We present two new approaches for the problem based on fixed-parameter algorithmics and integer linear programming. In contrast to previously used heuristics, our approaches compute provably optimal solutions. Conclusion Our computational results demonstrate that our exact algorithms are by far more efficient in practice than a previously used heuristic approach. In addition to the superior running time performance, our algorithms are capable of enumerating all optimal solutions, and naturally solve the weighted version of the problem.