Merging of biomedical decision diagrams

Abstract

Entscheidungsdiagramme sind ein beliebtes und wichtiges Hilfsmittel in medizinischen Anwendungen. Einer ihrer Hauptvorteile im Vergleich zu anderen Formalismen, wie etwa Regelsystemen, ist ihre intuitive Verständlichkeit. Dies gilt nicht nur für technische Fachkräfte sondern auch für Mediziner und administratives Personal.<br />Anwendungsszenarien finden sich unter anderem in der Durchführung von Screening-Tests, bei der Klassifizierung von DNA oder in mehrdimensionalen Datenstrukturen. Bei Screening-Tests werden üblicherweise zuerst verschiedene Informationen über den Patienten erhoben. Dazu zählen beispielsweise Blutwerte, Daten aus der Krankengeschichte und Informationen über die Lebensführung und gegebenenfalls Daten aus bildgebenden Verfahren. Anschließend gilt es zu entscheiden, ob der Patient Symptome für das Vorhandensein einer bestimmten Krankheit zeigt. Ist das der Fall, so ist eine genauere Untersuchung durch einen Arzt angebracht. Die Entscheidungsprozedur bis zu diesem Ergebnis lässt sich elegant als Entscheidungsbaum oder -diagramm darstellen, wie das auch in vielen medizinischen Leitlinien gemacht wird. Die inneren Knoten fragen Patientendaten ab, an den Blattknoten ist schließlich die ja/nein-Entscheidung abzulesen.<br />Ein weiteres Anwendungsbeispiel ist die Klassifizierung von DNA-Sequenzen in der Molekularbiologie. Heutzutage werden riesige Mengen an DNA automatisch sequenziert und die Performance der eingesetzten Verfahren hat beeindruckende Ausmaße angenommen. Der nächste Schritt ist es, aus diesen Sequenzen nützliche und nutzlose Teilsequenzen, sogenannte junk-DNA, herauszufiltern und eine Einteilung vorzunehmen.<br />Dazu können Sets von statistischen Features angewendet werden, die sich für jede beliebige Basenfolge berechnen lassen. Von einigen Features weiß man, dass sie sich signifikant zwischen codierender und nicht-codierender DNA unterscheiden und daher für die Klassifikation geeignet sind.<br />Diese beiden Beispiele demonstrieren die Relevanz von Entscheidungsdiagrammen in der Biomedizin. In dieser Arbeit wird weiters argumentiert, dass manchmal nicht nur einzelne Diagramme von Bedeutung sind, sondern mehrere, die einander zwar ähnlich aber nicht völlig äquivalent sind. Dies kann beispielsweise daher kommen, dass sie von unterschiedlichen Autoren stammen, die in ihren Studien zu ähnlichen Ergebnissen gekommen sind, die sich aber aufgrund statistischer Schwankungen geringfügig unterscheiden. In diesem Fall ist es wünschenswert ein automatisiertes System für die Vereinigung der Diagramme zur Verfügung zu haben. Dadurch wird der Benutzer von der Notwendigkeit für manuelle Zusammenführung befreit.<br />Deshalb ist es Ziel dieser Arbeit, eine derartige Prozedur zu entwickeln. Im technischen Teil wird der Open-Source-Reasoner dlvhex verwendet, für den ein Plugin entwickelt wird, das es zuerst ermöglicht überhaupt Entscheidungsdiagramme verarbeiten zu können, um diese schließlich in einem späteren Schritt zu vereinen. Das Vereinen selbst ist natürlich stark applikationsabhängig, das heißt es gibt nicht einen besten Algorithmus der in jedem Fall zum Ziel führt. Aus diesem Grund werden unterschiedliche Varianten implementiert die eine möglichst breite Palette von Szenarien abdecken. Nutzen und Stärke des Plugins ist die Möglichkeit, ohne manuelles Zusammenführen unterschiedliche Strategien ausprobieren zu können. Wie man aus Erkenntnissen des Bereichs Machine Learning weiß, ist die Qualität des Endergebnisses stark von den Trainingssets, den Trainingsalgorithmen und - im Falle von Multi-Classifier-Systemen - den Aggregatprozeduren abhängig. Das Testen und Evaluieren der Möglichkeiten wird in der vorliegenden Arbeit teilautomatisiert und daher wesentlich vereinfacht. Die Software wird schließlich demonstriert, indem wir das Beispiel der DNA-Klassifizierung im Detail betrachten.<br />

Decision diagrams are an important decision aid in medical applications. One of their main advantages compared with other formalisms like production rules is that they are intuitively understandable by clinicians, health care and administration personal.<br />It is not necessary to be an expert in information systems to act according to a diagram.<br />Possible application scenarios are medical screening tests, classification of DNA or multidimensional data structures. In screening tests, we usually collect certain chunks of information about the patient. This includes current disorders (if any), blood values, the medical history and data about the personal life style. In certain cases, additional results from image processing techniques like computer tomography can be added. Then we need to decide if this patient shows evidence for the disease in question or not. If this is the case, a medical expert will take a closer look at the patient and request further tests. This procedure can elegantly be represented as decision tree or diagram. The inner nodes refer to some data about the patient and the leaf nodes deliver the answer "yes" or "no".<br />Another scenario is the classification of DNA in molecular biology.<br />Today, the procedures for automatically sequencing the DNA of organisms have reached remarkable performance. Therefore the next task is to divide the useful subsequences, which encode for proteins from the rest, called junk DNA. This can be done by statistical features that are computed for a given sequence, and which vary significantly between coding and non-coding DNA.<br />These two examples show the relevance of decision diagrams in biomedicine. In this thesis it will be argued, that not only standalone diagrams are of importance, but that we can find scenarios where several similar but not equivalent diagrams have to be merged into a single one.<br />It is highly desirable to have an automatic or semi-automatic procedure that supports this process in order to take the burden of routine tasks from the user. Therefore it will be shown how such a tool can be implemented. Technically we will use dlvhex, an open-source reasoner for hex programs. A plugin for dlvhex will be developed, that adds support for decision diagram processing in general and merging in particular.<br />The actual merging step is strongly application dependent, i.e., there does not exist one correct result. This problem will be regarded by providing different merging algorithms, where the user can select an appropriate one.<br />The strength of the plugin and the actual benefit for the user is the possibility to try out different merging algorithms quickly, which makes it possible to focus on the most interesting tasks like algorithm optimization and result evaluation, whereas routine tasks are performed by the plugin. Finally this tool will be demonstrated when we take a closer look at the DNA classification example.