Using Temporal Reasoning for Genome Map Assembly

Proceedings of the Twentieth International Conference on Machine Learning, 1995

Volume

Proceedings of the Twentieth International Conference on Machine Learning, 1995

Contents

Genomic maps are an indispensable tool for molecular biologists; their modelling has to take into account representation as well as computational issues. The algorithmic complexity of the assembly task is already huge and is even made worse when one wishes to deal with inconsistencies and provide generic tools. This work presents an algorithm tackling the assembly problem by using temporal reasoning techniques. The algorithm has to transform the initial input data, i.e. qualitative and quantitative relations between entities that appear on the maps, so that temporal reasoning algorithms can be applied successfully; this is achieved by performing a partition of these relations upon their relative orientation, creating islets of relations in which reasoning mechanisms are applied. The implementation of the algorithm is based on a temporal reasoning software, taken as is, which gives a high genericity since any improvement in this software (such as efficiency or the management of flexible constraints) can be immediately used by the algorithm.