ABSTRACT
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.
Subject(s)
Algorithms , Chromosome Mapping , Human Genome Project , Models, Genetic , DNA/chemistry , DNA/genetics , Humans , Neural Networks, ComputerABSTRACT
Large scale genome sequencing projects are now producing hugh amounts of data which can be readily stored and managed within data base management systems, and analyzed using dedicated software packages. The results of these analyzes should also be stored with the input DNA sequences. The increasing complexity and size of the objects to be described and managed have led biologists to rely on advanced data models such as the object-oriented model. As a joint effort between our computer science and molecular biology research projects, the knowledge bases we have developed in molecular genetics have shown however that the basic object-oriented model is not fully adapted to the complexity of some biological situations encountered. Advanced descriptive capabilities, provided only by knowledge models originated from the AI field, are required. Composite or evolving objects, multiple viewpoints, constraints, tasks and methods, textual annotations are some examples of such capabilities. They are illustrated by biological situations for which they appeared to be necessary. Supporting powerful reasoning mechanisms (e.g. object classification, constraint propagation or qualitative simulators), they allow the development of large knowledge bases in molecular biology. These knowledge bases are expected to become the adequate support for co-operative distributed research efforts.