Engineering Fixed Parameter Algorithms for the Cluster Editing Problem
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
2022-03-21
Department
Major/Subject
Computer Science
Mcode
SCI3042
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
78
Series
Abstract
Cluster Editing is the problem of finding the minimum number of edge modifications that transform a given graph into a disjoint union of cliques. This is equivalent to finding optimal groups for a given set of objects and a symmetric binary relation over them, when the target is to minimize similarity across groups and maximize it within the groups. Even though the problem is NP-complete, it admits polynomial-time algorithms when the number of edge modifications is fixed a constant. The problem lends itself to various different applications, especially in the field of bioinformatics, where Cluster Editing algorithms have been used in genome sequencing, transcriptome analysis, and gene set classification, to name a few examples. The main contribution of this thesis is the implementation of a branching algorithm for the Cluster Editing problem, by evaluating and combining parts from existing published solutions. Although the problem is defined on unweighted graphs, the implemented algorithm first transforms the input instance into an integer-weighted graph, and then operates on this for the remainder of its run. This transformation makes it possible to use the edge-merging strategy of Böcker et al. (COCOA, 2008), which is one of the key parts enabling the common-case-fast behavior of the algorithm. The implemented algorithm is evaluated by timing its performance on a graph set containing instances of varying levels of difficulty. Two other solutions are also evaluated in the same way: the standard ILP formulation for Cluster Editing by Grötschel and Wakabayashi (Math. Program., 1989) solved using CBC, and KaPoCE, a branching Cluster Editing solver by Bläsius et al. (IPEC, 2021). Out of the three compared solutions, KaPoCE fared the best, solving the most instances in total and being the fastest to solve all but the easiest instances. These results are analyzed, and the analysis is used as a base to suggest future directions for research.Ekvivalenssimuokkaus (eng. Cluster Editing) on verkon muokkausongelma, jonka tarkoituksena on löytää pienin vaadittava määrä kaarenpoistoja ja -lisäyksiä, jolla annettu verkko voidaan muuntaa erillisten klikkien yhdisteeksi. Tämä voidaan myös nähdä optimaalisten ryhmien löytämisongelmana, missä syöte muodostuu joukosta kappaleita sekä binäärisestä ja symmetrisestä samankaltaisuusrelaatiosta näiden välillä. Vaikka ongelma on NP-täydellinen, voidaan se ratkaista polynomisessa ajassa kiinnittämällä kaarimuokkauksien maksimimäärä vakioksi. Ongelmalle on löydetty lukuisia sovellutuksia, erityisesti bioinformatiikan saralla, jossa Ekvivalenssimuokkaus-algoritmeja on käytetty muun muassa perimän sekvensointiin, transkriptomianalyysiin, sekä geenijoukkojen luokitteluun. Tämän työn päätulos on toteutus haarautuvalle Ekvivalenssimuokkaus algoritmille. Algoritmi toteutettiin arvioimalla ja yhdistelemällä tekniikoita ja mallintamalla työstettävä ongelmatapaus täydellisenä painotettuna verkkona. Painotetun verkon käyttäminen mahdollistaa solmujen yhdistämisen, mikä on yksi yhdistävä toimintatapa monen käytännössä tehokkaan haarautuvan algoritmin välillä kyseiselle ongelmalle. Toteutuksen suorituskyky määritettiin mittaamalla kuinka nopeasti se ratkaisee vaihtelevan vaikeustason ongelmatapauksia. Myös kaksi muuta ratkaisijaa mitattiin identtisellä tavalla: CBC-kokonaislukuohjelmaratkaisija, jolle annettiin vakiomuotoilu jokaisesta tarkasteltavasta ongelmatapauksesta, sekä KaPoCE, yksi tällä hetkellä nopeimmista haarautuvista Ekvivalenssimuokkaus-algoritmeista. Vertailluista ratkaisijoista nopein oli KaPoCE, joka ratkoi nopeiten kaikki paitsi helpoimmat tapaukset sekä myös suurimman kokonaismäärän ongelmatapauksia annetun aikamääreen sisällä. Näin saatuja tuloksia verrattiin keskenään, ja työssä ehdotetaan niiden perusteella suuntia jatkokehitykselle.Description
Supervisor
Kaski, PetteriThesis advisor
Kaski, PetteriKeywords
algorithm, cluster editing, clustering, exponential time, fixed- parameter tractability, graph