JK
J. Keur
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
In biology, phylogenetics is the study of the evolutionary history of and relations between e.g. species. Such data are often represented in trees. Remarkably, trees lack the representation of reticulation events, such as hybridization, while such events are believed to be important. One of the reasons why trees are widely used, is the enormous complexity of inferring a network directly from DNA data.
Therefore, indirect approaches are studied. One option is to construct a network from trees, which have been constructed from DNA data. Another option, which is studied in this work, is to create a network which represents all clusters from the trees. We are interested in finding a network having the lowest level possible, i.e. the lowest number of reticulations per biconnected component. The Cass algorithm is one of the best algorithms in this respect. However, it does not always give optimal results. In this thesis, an optimal algorithm is presented called STCass, of which many ideas are inspired from Cass. We lay
theoretical foundations on how to build an optimal network. Furthermore, (greedy) steps are proposed to solve the problem, which seem to work very well in practice. Based on several optimizations that are proposed, an improved algorithm called MSTCass is presented, which runs faster than STCass, in general. In order to speed up any Cass-based algorithm or derivatives of it, several lower bounds are presented on the reticulation number r(N) per biconnected component N of an optimal network. Besides, a new upper bound on r(N) is conjectured which can be evaluated in seconds, although e.g. an upper bound obtained by the HybridInterleave or PIRN algorithm is mostly lower and which can be evaluated often in twenty minutes for the tested instances. ...
Therefore, indirect approaches are studied. One option is to construct a network from trees, which have been constructed from DNA data. Another option, which is studied in this work, is to create a network which represents all clusters from the trees. We are interested in finding a network having the lowest level possible, i.e. the lowest number of reticulations per biconnected component. The Cass algorithm is one of the best algorithms in this respect. However, it does not always give optimal results. In this thesis, an optimal algorithm is presented called STCass, of which many ideas are inspired from Cass. We lay
theoretical foundations on how to build an optimal network. Furthermore, (greedy) steps are proposed to solve the problem, which seem to work very well in practice. Based on several optimizations that are proposed, an improved algorithm called MSTCass is presented, which runs faster than STCass, in general. In order to speed up any Cass-based algorithm or derivatives of it, several lower bounds are presented on the reticulation number r(N) per biconnected component N of an optimal network. Besides, a new upper bound on r(N) is conjectured which can be evaluated in seconds, although e.g. an upper bound obtained by the HybridInterleave or PIRN algorithm is mostly lower and which can be evaluated often in twenty minutes for the tested instances. ...
In biology, phylogenetics is the study of the evolutionary history of and relations between e.g. species. Such data are often represented in trees. Remarkably, trees lack the representation of reticulation events, such as hybridization, while such events are believed to be important. One of the reasons why trees are widely used, is the enormous complexity of inferring a network directly from DNA data.
Therefore, indirect approaches are studied. One option is to construct a network from trees, which have been constructed from DNA data. Another option, which is studied in this work, is to create a network which represents all clusters from the trees. We are interested in finding a network having the lowest level possible, i.e. the lowest number of reticulations per biconnected component. The Cass algorithm is one of the best algorithms in this respect. However, it does not always give optimal results. In this thesis, an optimal algorithm is presented called STCass, of which many ideas are inspired from Cass. We lay
theoretical foundations on how to build an optimal network. Furthermore, (greedy) steps are proposed to solve the problem, which seem to work very well in practice. Based on several optimizations that are proposed, an improved algorithm called MSTCass is presented, which runs faster than STCass, in general. In order to speed up any Cass-based algorithm or derivatives of it, several lower bounds are presented on the reticulation number r(N) per biconnected component N of an optimal network. Besides, a new upper bound on r(N) is conjectured which can be evaluated in seconds, although e.g. an upper bound obtained by the HybridInterleave or PIRN algorithm is mostly lower and which can be evaluated often in twenty minutes for the tested instances.
Therefore, indirect approaches are studied. One option is to construct a network from trees, which have been constructed from DNA data. Another option, which is studied in this work, is to create a network which represents all clusters from the trees. We are interested in finding a network having the lowest level possible, i.e. the lowest number of reticulations per biconnected component. The Cass algorithm is one of the best algorithms in this respect. However, it does not always give optimal results. In this thesis, an optimal algorithm is presented called STCass, of which many ideas are inspired from Cass. We lay
theoretical foundations on how to build an optimal network. Furthermore, (greedy) steps are proposed to solve the problem, which seem to work very well in practice. Based on several optimizations that are proposed, an improved algorithm called MSTCass is presented, which runs faster than STCass, in general. In order to speed up any Cass-based algorithm or derivatives of it, several lower bounds are presented on the reticulation number r(N) per biconnected component N of an optimal network. Besides, a new upper bound on r(N) is conjectured which can be evaluated in seconds, although e.g. an upper bound obtained by the HybridInterleave or PIRN algorithm is mostly lower and which can be evaluated often in twenty minutes for the tested instances.
Building a working quantum computer brings many challenges to overcome. For quanum processors, promising qubits seem to be NV-centres in diamond. Such processor is divided into processing units (PUs), each comprising an NV-centre with several carbon spin qubits, and they are interconnected with each other by optical links. The qubits within a PU can be modelled as nodes in a star graph and the optical connections as connections between the centres of the star graphs, such that the centres with their interconnections form a complete graph. We call the overall graph a fully connected star graph. In order to execute a quantum circuit, multiple pairs of qubits should be brought together in PUs at different times, which requires planning. Sorting the qubits is done via swaps. A swap within a PU can be performed easily, however, swapping between different PUs is done by teleportation, which is much more costly. Therefore, we neglect the costs of swaps within PUs. Parallellisation of swaps between PUs is done in a step. The less steps are used, the faster the quantum circuit is executed. In practice, as we are interested in fast computations, we often want to minimize the number of steps. The following problem is addressed. Given a current distribution of the qubits over the nodes in the fully connected star graph, and given a wanted, permuted distribution, minimize the number of swaps and/or steps to route the qubits from the current to the wanted distribution. At the moment, no efficient algorithm exists to sort the qubits especially in fully connected star graphs. Efficient solutions are presented in the form of algorithms. It is shown that qubit moves in fully connected star graphs can be scheduled efficiently, such that the number of moves is minimized. Guide lines are given to minimize the execution time too.
...
Building a working quantum computer brings many challenges to overcome. For quanum processors, promising qubits seem to be NV-centres in diamond. Such processor is divided into processing units (PUs), each comprising an NV-centre with several carbon spin qubits, and they are interconnected with each other by optical links. The qubits within a PU can be modelled as nodes in a star graph and the optical connections as connections between the centres of the star graphs, such that the centres with their interconnections form a complete graph. We call the overall graph a fully connected star graph. In order to execute a quantum circuit, multiple pairs of qubits should be brought together in PUs at different times, which requires planning. Sorting the qubits is done via swaps. A swap within a PU can be performed easily, however, swapping between different PUs is done by teleportation, which is much more costly. Therefore, we neglect the costs of swaps within PUs. Parallellisation of swaps between PUs is done in a step. The less steps are used, the faster the quantum circuit is executed. In practice, as we are interested in fast computations, we often want to minimize the number of steps. The following problem is addressed. Given a current distribution of the qubits over the nodes in the fully connected star graph, and given a wanted, permuted distribution, minimize the number of swaps and/or steps to route the qubits from the current to the wanted distribution. At the moment, no efficient algorithm exists to sort the qubits especially in fully connected star graphs. Efficient solutions are presented in the form of algorithms. It is shown that qubit moves in fully connected star graphs can be scheduled efficiently, such that the number of moves is minimized. Guide lines are given to minimize the execution time too.