PMC:1592098 / 16117-18378 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1592098","sourcedb":"PMC","sourceid":"1592098","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1592098","text":"Conclusion\nWe have constructed an algorithm for finding the quartet distance between two trees of arbitrary degree. It runs in time O(n + |V||V'| min{id, id'}) and uses space O(n + |V||V'|), where n is the number of leaves in the trees, |V| and |V'| are the number of internal nodes in the trees and id and id' are the maximal internal degree of internal nodes in input tree T and T' respectively. Internal degree of an internal node is the number of internal nodes connected to it, so neighbouring leaves do not add to this value. The values |V|, |V'|, id and id' are not independent, therefore we have investigated how the structure of the trees affect the running time of the algorithm. We show that the time used to count the butterfly quartets – topologies where one pair of the four leaves is separated from the other pair by an edge – is reduced to O(n2) when min{id, id'} = O(dmin2 MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaacqWGKbazdaqhaaWcbaacbiGae8xBa0Mae8xAaKMae8NBa4gabaGaeGOmaidaaaaa@333E@), where dmin is the minimal degree of all internal nodes in the trees. If the input trees are d-ary, that is all internal nodes have degree d, the running time is O(n2d MathType@MTEF@5@5@+=feaafiart1ev1aaatCvAUfKttLearuWrP9MDH5MBPbIqV92AaeXatLxBI9gBaebbnrfifHhDYfgasaacH8akY=wiFfYdH8Gipec8Eeeu0xXdbba9frFj0=OqFfea0dXdd9vqai=hGuQ8kuc9pgc9s8qqaq=dirpe0xb9q8qiLsFr0=vr0=vr0dc8meaabaqaciaacaGaaeqabaqabeGadaaakeaadaWcaaqaaiabd6gaUnaaCaaaleqabaGaeGOmaidaaaGcbaGaemizaqgaaaaa@309B@), excluding the time to find intersections. These theoretical running times have been validated by running a series of tests using a Java implementation of the algorithm, available at [15]. We also done a series of tests on random trees, trees generated by the program r8s, Buneman trees, and refined Buneman trees. Running the algorithm on these trees gives an impression on how it performs on trees used in practice. On both types of trees the running time appears to be O(n2). It is however still an open problem to develop an algorithm running in time O(n2)for all types of trees.","divisions":[{"label":"title","span":{"begin":0,"end":10}}],"tracks":[]}