On optimal comparability editing with applications to molecular diagnostics

摘要：

Background: The COMPARABILITY EDITING 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.Conclusions: 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.

作者: Sebastian B(o)cker Sebastian Briesemeister Gunnar W.Klau

作者单位: Institut für Informatik, Friedrich-Schiller-Universit(a)t, Jena, Germany Jena Centre for Bioinformat Institut für Informatik, Friedrich-Schiller-Universit(a)t, Jena, Germany Div.For Simulation of Biolo CWI, P.O.Box 94079, 1090 GB Amsterdam, The Netherlands All authors contributed equally to this work

会议类型: 国际会议

会议名称: The 7th Asia-Pacific Bioinformatics Conference(第七届亚太生物信息学大会)

会议地点: 北京

会议语种:英文

页码: 673-682

在线出版日期: 2009-01-01（万方平台首次上网日期，不代表论文的发表时间）