{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,28]],"date-time":"2023-01-28T02:09:06Z","timestamp":1674871746510},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"S1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>The C<jats:sc>OMPARABILITY<\/jats:sc> E<jats:sc>DITING<\/jats:sc> problem appears in the context of hierarchical disease classification based on noisy data. We are given a directed graph <jats:italic>G<\/jats:italic> representing hierarchical relationships between patient subgroups. The task is to identify the minimum number of edge insertions or deletions to transform <jats:italic>G<\/jats:italic> into a transitive graph, that is, if edges (<jats:italic>u<\/jats:italic>, <jats:italic>v<\/jats:italic>) and (<jats:italic>v<\/jats:italic>, <jats:italic>w<\/jats:italic>) are present then edge (<jats:italic>u<\/jats:italic>, <jats:italic>w<\/jats:italic>) must be present, too.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusion<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1471-2105-10-s1-s61","type":"journal-article","created":{"date-parts":[[2009,1,30]],"date-time":"2009-01-30T20:05:18Z","timestamp":1233345918000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["On optimal comparability editing with applications to molecular diagnostics"],"prefix":"10.1186","volume":"10","author":[{"given":"Sebastian","family":"B\u00f6cker","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Briesemeister","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gunnar W","family":"Klau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,1,30]]},"reference":[{"issue":"7","key":"3244_CR1","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1093\/bioinformatics\/btn056","volume":"24","author":"J Jacob","year":"2008","unstructured":"Jacob J, Jentsch M, Kostka D, Bentink S, Spang R: Detecting hierarchical structure in molecular characteristics of disease using transitive approximations of directed graphs. Bioinformatics. 2008, 24 (7): 995-1001.","journal-title":"Bioinformatics"},{"issue":"23","key":"3244_CR2","doi-asserted-by":"publisher","first-page":"2419","DOI":"10.1056\/NEJMoa055351","volume":"354","author":"M Hummel","year":"2006","unstructured":"Hummel M: A biologic definition of Burkitt's lymphoma from transcriptional and genomic profiling. N Engl J Med. 2006, 354 (23): 2419-2430.","journal-title":"N Engl J Med"},{"issue":"9","key":"3244_CR3","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1007\/s00236-004-0144-0","volume":"40","author":"S Delvaux","year":"2004","unstructured":"Delvaux S, Horsten L: On best transitive approximations to simple graphs. Acta Inform. 2004, 40 (9): 637-655.","journal-title":"Acta Inform"},{"key":"3244_CR4","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/3-540-46784-X_8","volume-title":"Proc. of Workshop on Graph-Theoretic Concepts in Computer Science (WG 1999)","author":"A Natanzon","year":"1999","unstructured":"Natanzon A, Shamir R, Sharan R: Complexity Classification of Some Edge Modification Problems. Proc. of Workshop on Graph-Theoretic Concepts in Computer Science (WG 1999). 1999, Lect. Notes Comput. Sc., Springer, 1665: 65-77."},{"issue":"3","key":"3244_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/BF00289116","volume":"23","author":"M K\u0159iv\u00e1nek","year":"1986","unstructured":"K\u0159iv\u00e1nek M, Mor\u00e1vek J: NP-Hard Problems in Hierarchical-Tree Clustering. Acta Inform. 1986, 23 (3): 311-323.","journal-title":"Acta Inform"},{"key":"3244_CR6","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/BF01589097","volume":"45","author":"M Gr\u00f6tschel","year":"1989","unstructured":"Gr\u00f6tschel M, Wakabayashi Y: A cutting plane algorithm for a clustering problem. Math Program. 1989, 45: 52-96.","journal-title":"Math Program"},{"issue":"4","key":"3244_CR7","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00224-004-1178-y","volume":"38","author":"J Gramm","year":"2005","unstructured":"Gramm J, Guo J, H\u00fcffner F, Niedermeier R: Graph-modeled data clustering: Fixed-parameter algorithms for clique generation. Theor Comput Syst. 2005, 38 (4): 373-392.","journal-title":"Theor Comput Syst"},{"key":"3244_CR8","first-page":"211","volume-title":"Proc. of Asia-Pacific Bioinformatics Conference (APBC 2008)","author":"S B\u00f6cker","year":"2008","unstructured":"B\u00f6cker S, Briesemeister S, Bui QBA, Tru\u00df A: A fixed-parameter approach for Weighted Cluster Editing. Proc. of Asia-Pacific Bioinformatics Conference (APBC 2008). 2008, Series on Advances in Bioinformatics and Computational Biology, Imperial College Press, 5: 211-220."},{"key":"3244_CR9","first-page":"289","volume-title":"Proc. of Workshop on Experimental Algorithms (WEA 2008)","author":"S B\u00f6cker","year":"2008","unstructured":"B\u00f6cker S, Briesemeister S, Klau GW: Exact Algorithms for Cluster Editing: Evaluation and Experiments. Proc. of Workshop on Experimental Algorithms (WEA 2008). 2008, Lect. Notes Comput. Sc., Springer, 5038: 289-302."},{"key":"3244_CR10","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier R: Invitation to Fixed-Parameter Algorithms. 2006, Oxford University Press"},{"key":"3244_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF02592097","volume":"73","author":"R M\u00fcller","year":"1996","unstructured":"M\u00fcller R: On the partial order polytope of a digraph. Mathematical Programming. 1996, 73: 31-49.","journal-title":"Mathematical Programming"},{"key":"3244_CR12","unstructured":"Klau GW: [web page]. [Accessed 25 September 2008], [http:\/\/www.planet-lisa.net]"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-10-S1-S61.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T02:55:00Z","timestamp":1630464900000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-10-S1-S61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":12,"journal-issue":{"issue":"S1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["3244"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-10-s1-s61","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]},"assertion":[{"value":"30 January 2009","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"S61"}}