Zugl.: München, Univ. der Bundeswehr, Diss., 2008

Zugl.: Hildesheim, Univ., Diss., 2009

Zugl.: Bremen, Univ., Diss., 2007.

Diese kumulative Dissertation umfaßt drei Publikationen, die im Folgenden kurz vorgestellt werden. Die erste Publikation befasst sich mit der Fragestellung aus der Populationsgenetik, ob Isolatpopulationen für die Erforschung genetischer Ursachen von Krankheiten oder quantitativen Phänotypen besser geeignet sind als nicht isolierte Populationen. Man erwartet aufgrund homogenerer Umwelteinflüsse, geringerer Anzahl kausaler genetischer Varianten und insbesondere durch homogenere Bereiche im Genom Vorteile bei der Identifikation genetischer Ursachen in Isolatpopulationen. Am Beispiel der Sorben, die einen gewissen Isolatcharakter aufweisen, sollte deshalb untersucht werden, inwieweit sich diese von einer deutschen populationsbasierten Studie wie KORA genetisch unterscheiden und welche Bedeutung die Unterschiede für genetische Assoziationsanalysen haben. In der ersten Publikation wird gezeigt, daß die Sorben Merkmale genetischer Isolation aufweisen, die nicht auf eine stärkere Verwandtschaftsstruktur der Studienpopulation gegenüber KORA zurückzuführen sind. Die Merkmale genetischer Isolation sind moderat, trotzdem ist der slawische Ursprung erkennbar. Daraus läßt sich schließen, daß die Sorben ursprünglich genetisch isoliert waren, jedoch die genetische Isolation verloren geht. Trotz Unterschiede in der SNP-Korrelationsstruktur durch ein im Mittel höheres Kopplungsungleichgewicht zwischen benachbarten SNPs ist kein klarer Vorteil bei der Power von SNP-Assoziationsanalysen zu erwarten. Die Verwandtschaftsstruktur der Sorben kann aber bei unkorrigierten SNP-Assoziationsanalysen zu einer Varianzinflation des Effektschätzers führen und die Power des Tests in komplexer Weise beeinflussen. Es sollte daher in einer weiteren Publikation geklärt werden, wie die Verwandtschaftsstruktur der Studienpopulation und die Heritabilität eines Phänotyps die Varianz des Effektschätzers und die Power des Tests tatsächlich beeinflussen. In der zweiten Publikation wird der Einfluß der Verwandtschaftsstruktur auf SNP-Assoziationsanalysen im Detail untersucht. Verwandtschaften in einer Studienpopulation führen zu korrelierten Phänotypen, was die Annahme unabhängiger Beobachtungen des einfachen linearen Modells verletzt. Aus empirischen Studien war zudem bekannt, daß eine stärkere Verwandtschaftsstruktur der Studienpopulation und eine größere Heritabilität des Phänotyps den Fehler erster Art eines unkorrigierten Tests vergrößern. Der Einfluß der Verwandtschaftsstruktur auf die Power wurde in empirischen Studien unterschiedlich beurteilt. Zudem wird genomic control häufig dazu verwendet, eine Inflation der Teststatistik durch Verwandtschaft zu korrigieren, jedoch führt genomic control zu einer Power-Reduktion. Auch diese empirischen Beobachtungen sollten erklärt werden. In der zweiten Publikation wird analytisch gezeigt, wie die Verwandtschaftsstruktur und die Heritabilität des Phänotyps mit der Varianzinflation des Effektschätzers und der Teststatistik zusammenhängen. Während der Fehler erster Art mit größerer Varianzinflation steigt, wird die Power in komplexer Weise beeinflußt. Ob die Power bei Varianzinflation größer oder kleiner wird, hängt von der Stärke des genetischen Effekts und vom Signifikanzniveau des Tests ab. Zudem konnten weitere empirische Beobachtungen aus der Literatur analytisch erklärt werden, zum Beispiel daß der Erwartungswert des Effektschätzers nicht durch Verwandtschaft beeinflußt wird, die empirische Varianz des Effektschätzers bei Verwandtschaft deflationiert ist und daß die Allelfrequenz des SNP nur einen geringen Einfluß auf die Varianzinflation hat. Weiterhin kann genomic control im Allgemeinen nicht für die Korrektur von Varianzinflation durch Verwandtschaft empfohlen werden. Obwohl der Fehler erster Art durch genomic control eingehalten wird, führt die Methode zu einem starken Power-Verlust in Abhängigkeit der Varianzinflation. Zur Bestimmung der Varianzinflation wurde eine Näherungsformel analytisch hergeleitet, die nur die Verwandtschaftsstruktur und die Heritabilität des Phänotyps benötigt. Aus der Publikation folgt, daß eine Varianzinflation kleiner als 1,05 keinen relevanten Einfluß auf den statistischen Test hat und die Verwendung des einfachen linearen Modells in diesem Fall angemessen ist. Ist die Varianzinflation größer, müssen Methoden wie beispielsweise gemischte Modelle im Rahmen einer SNP-Assoziationsanalyse verwendet werden, welche explizit die Verwandtschaftsstruktur berücksichtigen. In der dritten Publikation wird ein weiteres Paradigma der Statistik betrachtet. Eine SNP-Assoziationsanalyse kann neben klassischen Methoden auch mit bayesianischen Methoden erfolgen. Bayesianische Methoden bieten dabei die Möglichkeit, SNP- und Phänotyp-Korrelationen zu berücksichtigen und so die Modellanpassung gegenüber der klassischen Analyse zu verbessern. Am Beispiel einer Kinderstudie sollte nach dem Einfluß bestimmter SNPs ausgewählter Kandidaten-Gene (SORT1, HMGCR, MLXIPL, FADS2, APOE, MAFB) auf Lipidkonzentrationen von HDL-C (high density lipoprotein cholesterol), LDL-C (low density lipoprotein cholesterol), TC (total cholesterol) und TG (triglyceride) gesucht werden, um auf genetische Ursachen für Parameter des Stoffwechsels in der frühen Entwicklung schließen zu können. In der dritten Publikation wurde zunächst eine klassische SNP-Assoziationsanalyse durchgeführt und ein Zusammenhang von SORT1 und APOE mit LDL-C und TC identifiziert. Darauf wurde in einer bayesianischen Analyse der mehrdimensionale Phänotyp aus HDL-C, LDL-C und TG modelliert, wodurch explizit die Phänotyp-Korrelationsstruktur berücksichtigt wurde. Für die einzelnen Lipidkonzentrationen wurde eine plausible Auswahl von Einflussfaktoren bestehend aus genetischen Varianten, Alter, Geschlecht und BMI unter Berücksichtigung verschiedener genetischer Modelle bestimmt. Dadurch wurden sowohl die Ergebnisse aus der klassischen Analyse bestätigt, als auch weitere Kandidaten, beispielsweise ein Zusammenhang zwischen MLXIPL und TG, gefunden. Ein wichtiges Ergebnis dieser Arbeit war zudem die Präsentation der bayesianischen Modellergebnisse in einfacher Form. Für die bayesianische Analyse wurden gegenüber der klassischen Analyse einige Vorteile festgestellt, die zukünftig weiter untersucht werden sollen. Dazu zählt die Berücksichtigung von Korrelationsstrukturen im bayesianischen Modell, die zu einer verbesserten Identifikation von Phänotyp-Genotyp-Beziehungen führen kann. Weiterhin lassen sich die bei der bayesianischen Modellauswahl identifizierten genetischen Effekte über alle Modelle mitteln, in denen die entsprechenden Variablen eingeschlossen wurden. Dadurch fallen die empirischen Varianzen der Effekte meist kleiner aus als die zugehörigen Varianzen der Beta-Schätzer aus der klassischen Analyse. Zuletzt werden bei der klassischen Analyse meist aufgrund einzelner Fehlwerte in Phänotypen, SNPs oder Kovariablen ganze Fälle verworfen, was zu einer erheblichen Fallzahlreduktion führen kann. Diese Fehlwerte können bei der bayesianischen Analyse als zusätzliche Parameter modelliert werden, wodurch die ursprüngliche Fallzahl erhalten bleibt. Diese Aspekte sollen zukünftig in Simulationsstudien untersucht werden, in denen der Einfluß von Korrelationsstrukturen, Effektstärken und Fehlwerten auf die Identifikation genetischer Effekte im Vergleich zur klassischen Analyse betrachtet wird.

In den vergangenen Jahren wurde vermehrt das Gen, welches für Catechol-O-Methyltransferase codiert, als starker Kandidat für ein erhöhtes Schizophrenierisiko diskutiert. Grund dafür ist die zentrale Rolle der Catechol-O-Methyltransferase beim Katecholaminabbau im menschlichen präfrontalen Cortex. Aufgrund der zunehmend akzeptierten Tatsache, daß die singuläre Betrachtung einzelner Marker bei der komplexen genetischen Textur von Kandidatengenen nur wenig zur Erhellung komplexer Erkrankungen beizutragen vermag (Licinio, 2003), untersuchten wir neben dem Val108/158Met-Polymorphismus (rs4680) vier weitere, die COMT-Gen-Region umspannende SNPs (rs2097603, rs740603, rs4818, rs165599) an einer Stichprobe von 459 Schizophrenen und 150 Kontrollpersonen. Zwar ergab sich für den Marker rs740603 auf Intron 1 eine signifikante Allel- (p = 0.0060) und Genotypassoziation (p = 0.019), der funktionelle Val108/158Met-Polymorphismus (rs4680) zeigte aber keinen signifikanten Zusammenhang mit der Erkrankung. Zudem fand sich in unserer Haplotypanalyse keine Markerkombination, die in überdurchschnittlichem Zusammenhang mit schizophrenen Psychosen stand. Für die Untergruppe der zykloiden Psychosen ließ sich bei einem p-Wert von 0.031 eine 4-Marker-Kombination ermitteln, die die SNPs rs740603, rs4818, rs4680 und rs165599 einschliesst und die Region von Intron 1 bis 3´-UTR umspannt. Zusätzlich ergab sich in der Subgruppe der zykloiden Psychosen ein geschlechtsspezifischer Effekt im Sinne eines signifikanten 3-Marker-Haplotypen (rs4818-rs4680-rs165599) (p = .0044) in der Gruppe der Frauen (n = 27) mit rs165599 als stärkstem Einzelmarker. Aufgrund des komplexen genetischen Zusammenhangs zwischen den untersuchten Markern und der Erkrankung sollte auch in der zukünftigen Forschung eine differenzierte Betrachtung der verschiedenen schizophrenen Zustandsbilder angestrebt werden, wie dies die Klassifikation nach Leonhard ermöglicht. Neben gewebsspezifischen Transkriptionsfaktoren könnten auch epigenetische Faktoren, wie die Cytosinmethylierung von CpG-Stellen in promotorregulierenden Regionen, einen Erklärungsansatz für die Entstehung schizophrener Störungsbilder darstellen. / Since several years, the gene encoding catechol-O-methyltransferase (COMT) at chromosome 22q11 is discussed as a strong candidate for schizophrenia susceptibility due to its key function in degredation of catecholamines in the prefrontal cortex, a critical region of the human brain, involved in cognitive control processes, monitoring of information in working memory and in active judgments on information (Petrides, 2005). To test the association of the COMT gene locus with schizophrenia, we analysed five SNPs (rs2097603, rs740603, rs4818, rs4680, rs165599) spanning from the P2 promotor region (MB-COMT) to the 3´-UTR in 459 index cases, which fulfilled diagnistic criteria of schizophrenia according to DSM IV as well as 150 blood donors as population controls. According to differentiated psychopathology (Leonhard, 1999) probands were categorized into cycloid psychosis, unsystematic schizophrenia and systematic schizophrenia prior to genotyping. In intron 1 the marker rs740603 showed significant allele (p = 0.0060) and genotype (p = 0.019) association, but the functional Val105/158Met variant (rs4680) failed significant association with disease. Considering COMT haplotypes none of the marker combinations showed evidence for an association with schizophrenia. In the subgroup of cycloid psychosis we found 4-locus marker combinations rs740603-rs4818-rs4680-rs165599 associated with disease at p-level 0.031, spanning a region from intron 1 to the 3´-UTR. In conclusion, the genetic interaction of COMT SNPs and haplotypes and schizophrenia susceptibility appears complex across different populations and psychopathological phenotypes. Particularly structures potentially involved in mRNA expression levels need further scrutiny.

In dieser Arbeit zu genetischen Analysen für die Vorbereitung eine markergestützten Selek-tion auf Trockenstresstoleranz bei der Winterackerbohne wurden 196 Winterackerbohnen-Inzuchtlinien und vier Sommerackerbohnen-Inzuchtlinien genotypisiert. Diese Inzuchtlinien wurden außerdem hinsichtlich der Physiologie-Merkmale Spad-Wert, Membranstabilitäts-index, Blattwassergehalt, Gesamtgehalt löslicher Zucker sowie Prolin- und Glycinbetainge-halt in je einer Kontroll- und einer Stressbehandlung phänotypisiert. Anhand eines Verifika-tionssatzes von 40 der 196 Winterackerbohnen-Inzuchtlinien wurden korrelative Verbin-dungen zwischen den physiologischen Merkmalen sowie feldbasierten und züchterisch relevanten Merkmalen wie bspw. Ertrag gesucht. Diese feldbasierten Merkmale wurden mit Hilfe von Rain-Out-Sheltern an den Standorten Göttingen und Groß Lüsewitz in den Jahren 2010/2011, 2012 und 2012/2013 erfasst. Ferner wurden die Möglichkeiten einer Simulation von Trockenstressreaktionen anhand dieses Verifikationssatzes durch Sikkationsversuche mit Kaliumjodidapplikation untersucht. Es konnten keine eindeutigen Beziehungen zwi-schen der Stressreaktion induziert durch Wassermangel und durch Kaliumjodidapplikation ermittelt werden. Außerdem wurden keine eindeutigen Beziehungen der physiologischen Merkmale zu den feldbasierten Trockenstressresultaten gefunden. Mittels einer Kartierungspopulation von 101 RIL wurde eine genetische Karte der Acker-bohne mit zwölf Kopplungsgruppen bestehend aus insgesamt 1451 Markern und einer Län-ge von 1633,2 cM erstellt. Fünf dieser Kopplungsgruppen konnten als Fragmente identifi-ziert werden. Die verbleibenden sieben Kopplungsgruppen wurden mit den verwendeten SNP-Markern mittelbar den sechs Chromosomen der Ackerbohne zugeordnet. Hierbei stel-len z. B. die erste und vierte Kopplungsgruppe gemeinsam eine Kopplungsgruppe dar. Die so kartierten Marker wurden hinsichtlich ihres Spaltungsverhältnisses innerhalb des A-Satzes – bestehend aus 189 der 196 phänotypisierten Winterackerbohnen-Inzuchtlinien – überprüft und für eine Assoziationsanalyse mit den Physiologiemerkmalen ausgewählt. Das Gametenphasenungleichgewicht zwischen 323 610 Markerpaaren wurde ihrer jeweiligen Distanz auf der genetischen Karte gegenübergestellt. Es konnte gezeigt werden, dass in der Entstehungsgeschichte des untersuchten Materials das Gametenphasenungleichgewicht durch Rekombination stark abgebaut wurde. In die Assoziationsanalyse flossen insgesamt 1322 Marker ein. Mittels dieser molekularen Marker konnten insgesamt sechs QTL für Physiologie-Merkmale identifiziert werden. Dabei entfiel je ein QTL auf die Merkmale absolute Differenz im Glycinbetaingehalt zwischen Stress- und Kontrollbehandlung und Glycinbetaingehalt in der Kontrollbehandlung. Vier QTL konnten für die absolute Differenz zwischen dem Prolingehalt in der Stress- und Kontroll-behandlung identifiziert werden. Die gefundenen QTL können anhand der vorliegenden feldbasierten Verifikationsdaten nicht als markergestützte Selektionsmöglichkeit auf Tro-ckenstresstoleranz empfohlen werden. Der nächste Schritt ist demzufolge, mittels feldba-sierter Prüfungen der Inzuchtlinien in realen, relevanten Trockenstresslagen über ausrei-chend viele Orte und Jahre die Bedeutung der physiologischen Merkmale weiter zu prüfen.

Frequent itemset mining is an important building block in many data mining applications like market basket analysis, recommendation, web-mining, fraud detection, and gene expression analysis. In many of them, the datasets being mined can easily grow up to hundreds of gigabytes or even terabytes of data. Hence, efficient algorithms are required to process such large amounts of data. In recent years, there have been many frequent-itemset mining algorithms proposed, which however (1) often have high memory requirements and (2) do not exploit the large degrees of parallelism provided by modern multiprocessor systems. The high memory requirements arise mainly from inefficient data structures that have only been shown to be sufficient for small datasets. For large datasets, however, the use of these data structures force the algorithms to go out-of-core, i.e., they have to access secondary memory, which leads to serious performance degradations. Exploiting available parallelism is further required to mine large datasets because the serial performance of processors almost stopped increasing. Algorithms should therefore exploit the large number of available threads and also the other kinds of parallelism (e.g., vector instruction sets) besides thread-level parallelism. In this work, we tackle the high memory requirements of frequent itemset mining twofold: we (1) compress the datasets being mined because they must be kept in main memory during several mining invocations and (2) improve existing mining algorithms with memory-efficient data structures. For compressing the datasets, we employ efficient encodings that show a good compression performance on a wide variety of realistic datasets, i.e., the size of the datasets is reduced by up to 6.4x. The encodings can further be applied directly while loading the dataset from disk or network. Since encoding and decoding is repeatedly required for loading and mining the datasets, we reduce its costs by providing parallel encodings that achieve high throughputs for both tasks. For a memory-efficient representation of the mining algorithms’ intermediate data, we propose compact data structures and even employ explicit compression. Both methods together reduce the intermediate data’s size by up to 25x. The smaller memory requirements avoid or delay expensive out-of-core computation when large datasets are mined. For coping with the high parallelism provided by current multiprocessor systems, we identify the performance hot spots and scalability issues of existing frequent-itemset mining algorithms. The hot spots, which form basic building blocks of these algorithms, cover (1) counting the frequency of fixed-length strings, (2) building prefix trees, (3) compressing integer values, and (4) intersecting lists of sorted integer values or bitmaps. For all of them, we discuss how to exploit available parallelism and provide scalable solutions. Furthermore, almost all components of the mining algorithms must be parallelized to keep the sequential fraction of the algorithms as small as possible. We integrate the parallelized building blocks and components into three well-known mining algorithms and further analyze the impact of certain existing optimizations. Our algorithms are already single-threaded often up an order of magnitude faster than existing highly optimized algorithms and further scale almost linear on a large 32-core multiprocessor system. Although our optimizations are intended for frequent-itemset mining algorithms, they can be applied with only minor changes to algorithms that are used for mining of other types of itemsets.

Frequent itemset mining is an important building block in many data mining applications like market basket analysis, recommendation, web-mining, fraud detection, and gene expression analysis. In many of them, the datasets being mined can easily grow up to hundreds of gigabytes or even terabytes of data. Hence, efficient algorithms are required to process such large amounts of data. In recent years, there have been many frequent-itemset mining algorithms proposed, which however (1) often have high memory requirements and (2) do not exploit the large degrees of parallelism provided by modern multiprocessor systems. The high memory requirements arise mainly from inefficient data structures that have only been shown to be sufficient for small datasets. For large datasets, however, the use of these data structures force the algorithms to go out-of-core, i.e., they have to access secondary memory, which leads to serious performance degradations. Exploiting available parallelism is further required to mine large datasets because the serial performance of processors almost stopped increasing. Algorithms should therefore exploit the large number of available threads and also the other kinds of parallelism (e.g., vector instruction sets) besides thread-level parallelism. In this work, we tackle the high memory requirements of frequent itemset mining twofold: we (1) compress the datasets being mined because they must be kept in main memory during several mining invocations and (2) improve existing mining algorithms with memory-efficient data structures. For compressing the datasets, we employ efficient encodings that show a good compression performance on a wide variety of realistic datasets, i.e., the size of the datasets is reduced by up to 6.4x. The encodings can further be applied directly while loading the dataset from disk or network. Since encoding and decoding is repeatedly required for loading and mining the datasets, we reduce its costs by providing parallel encodings that achieve high throughputs for both tasks. For a memory-efficient representation of the mining algorithms’ intermediate data, we propose compact data structures and even employ explicit compression. Both methods together reduce the intermediate data’s size by up to 25x. The smaller memory requirements avoid or delay expensive out-of-core computation when large datasets are mined. For coping with the high parallelism provided by current multiprocessor systems, we identify the performance hot spots and scalability issues of existing frequent-itemset mining algorithms. The hot spots, which form basic building blocks of these algorithms, cover (1) counting the frequency of fixed-length strings, (2) building prefix trees, (3) compressing integer values, and (4) intersecting lists of sorted integer values or bitmaps. For all of them, we discuss how to exploit available parallelism and provide scalable solutions. Furthermore, almost all components of the mining algorithms must be parallelized to keep the sequential fraction of the algorithms as small as possible. We integrate the parallelized building blocks and components into three well-known mining algorithms and further analyze the impact of certain existing optimizations. Our algorithms are already single-threaded often up an order of magnitude faster than existing highly optimized algorithms and further scale almost linear on a large 32-core multiprocessor system. Although our optimizations are intended for frequent-itemset mining algorithms, they can be applied with only minor changes to algorithms that are used for mining of other types of itemsets.