An algebraic structure is finitely related if its clone is determined by a finite set of finitary relations. In this thesis we examine graph algebras in order to determine which of them have this property. We provide a brief sum- mary of a background theory and we present an overview of known results, in particular, we emphasize the relation between finitely related algebras and Mal'cev conditions. Further we present basic results about the structure of graph algebras. The main part of this thesis is a partial classification of finitely related graph algebras. We provide proofs for various classes of graph algebras, for example for algebras defined by connected bipartite graphs or algebras de- fined by graphs containing certain subgraphs, although several cases are missing to complete the classification. 1

The methods presented in this study are aimed at the identification of subpopulations (clones) of genetically similar cells within tissue samples through measurement of loci-specific Fluorescence in-situ hybridization (FISH) spot signals for each nucleus and analyzing cell spatial distributions by way of Voronoi tessellation and Delaunay triangulation to robustly define cell neighbourhoods. The motivation for the system is to examine lung cancer patient for subpopulations of Non-Small Cell Lung Cancer (NSCLC) cells with biologically meaningful gene copy-number profiles: patterns of genetic alterations statistically associated with resistance to cis-platinum/vinorelbine doublet chemotherapy treatment. Current technologies for gene-copy number profiling rely on large amount of cellular material, which is not always available and suffers from limited sensitivity to only the most dominant clone in often heterogeneous samples. Thus, through the use of FISH, the detection of gene copy-numbers is possible in unprocessed tissues, allowing identification of specific tumour clones with biologically relevant patterns of genetic aberrations. The tissue-wide characterization of multiplexed loci-specific FISH signals, described herein, is achieved through a fully automated, multicolour fluorescence imaging microscope and object segmentation algorithms to identify cell nuclei and FISH spots within. Related tumour clones are identified through analysis of robustly defined cell neighbourhoods and cell-to-cell connections for regions of cells with homogenous and highly interconnected FISH spot signal characteristics. This study presents experiments which demonstrate the system’s ability to accurately quantify FISH spot signals in various tumour tissues and in up to 5 colours simultaneously or more through multiple rounds of FISH staining. Furthermore, the system’s FISH-based cell classification performance is evaluated at a sensitivity of 84% and specificity 81% and clonal identification algorithm results are determined to be comparable to clone delineation by a human-observer. Additionally, guidelines and procedures to perform anticipated, routine analysis experiments are established. / Science, Faculty of / Physics and Astronomy, Department of / Graduate

Workshop cluster 1 (WC1) molecules are exclusively expressed on the surface of gamma delta T cells and act as co-receptors and bind pathogens thus also functioning as pattern recognition receptors. The aim was to obtain cDNA evidence to support the recent caprine genome annotation of the WC1 multigene family conducted by a colleague. To get cDNA sequences three strategies were used. Strategy 'I' was used to obtain three clones that corresponded to WC1 SRCR domain d9 through the intracytoplasmic tail sequence. Strategy 'II' was used to obtain 6 clones. A PCR was conducted using SRCR domain b7 through the intracytoplasmic tail sequence. A third strategy obtained full-length WC1 transcripts. The three sequences that extended from SRCR domain d9 to the intracytoplasmic tail matched closely with predicted goat Gene 1 or 14. Another 3 sequences that extended from the SRCR b7 domain through SRCR domain d11 or through the intracytoplasmic tail matched with the predicted Genes 1, 2 and 14, respectively. Two additional full-length cDNA clones CH-MA-03 and 41 were completely sequenced in stages which involved a PCR amplication of the internal domains to complete the sequencing. The a1 domain of CH-MA41 was 100% similar to the annotated and predicted Gene 4 while CH-MA03 also was closest to Gene 4 with a 99% similarity. However, the intracytoplasmic tail sequence of these two cDNA clones was a Type II tail while Gene 4 had a Type I tail. Because of this difference in tails these two cDNA clones had a greater overall similarity with Genes 7 and 15 which had Type II tails. These results suggest that the genome assembly may have errors.

Bei der Entwicklung von Programmen werden durch Entwickler regelmäßig Code-Clones durch das Kopieren von Quellcode erzeugt. In dieser Arbeit wird ein Ansatz zur automatisierten Messung dieses duplizierten Codes mit Hilfe von Clone-Detection-Tools über mehrere Versionen von verschiedenen Software-Produkten gezeigt. Anhand der Historien von Code-Clones werden Einflüsse auf die Redundanzen dieser Software empirisch gemessen. Damit wird eine Grundlage für den Beweis, dass die Entwicklung von Programmiersprachen zu einem dominanten Teil durch Redundanzreduzierung getrieben wird, geschaffen.:Inhaltsverzeichnis Abstract I Inhaltsverzeichnis II 1 Einleitung 1 1.1 Problemstellung 1 1.2 Zielsetzung 1 1.3 Vorgehensweise 3 2 Vorbetrachtung 5 2.1 Programmierkonzepte 5 2.1.1 Definition 5 2.1.2 Programmierkonzepte in Java 5 2.2 Treiber für die Entwicklung von Programmierkonzepten 8 2.2.1 Arten der Treiber von Programmierkonzepten 9 2.2.2 Reduzierung von Redundanz in Software 10 2.2.2.1 Arten von Redundanz in Software 10 2.2.2.2 Code-Clones 11 2.2.2.3 Folgen von Redundanz in Software 13 2.2.3 Ansätze für den Nachweis von Redundanzreduzierung als Treiber 14 2.3 Auswahl Software Repositories für die Analysen 16 2.3.1 Arten von Software Repositories 16 2.3.2 Anforderung an Software Repositories 17 3 Erhebungsprozess für die Analyse von Software auf Clones 20 3.1 Aufbau des Erhebungsprozesses 20 3.1.1 Lösungsansatz 20 3.1.2 Prozessteuerung 21 3.2 Umgang mit Versionierung 22 3.2.1 Allgemein 22 3.2.2 Commit-Filter 24 3.3 Clone-Detection 25 3.3.1 Arten und Vertreter 25 3.3.2 Eigene Verwendung 28 3.3.2.1 Simian 28 3.3.2.2 CCFinderX 29 3.3.3 Laufzeitproblem und Lösungsansätze 31 3.4 Datenaggregation 32 4 Auswertung der Messungen 35 4.1 Vorgehensweise der Auswertung 35 4.2 Betrachtung von Code-Clone-Historien 35 4.3 Vergleich unterschiedlicher Konfigurationen 41 4.3.1 Vergleich unterschiedlicher Clone-Detection-Tools 41 4.3.2 Vergleich unterschiedlicher Commit-Filter 45 4.3.3 Vergleich unterschiedlicher Schwellwerte für die Erkennung 46 4.4 Untersuchung verschiedener Interessenpunkte 48 5 Nachbetrachtung 53 5.1 Fehlerbetrachtung 53 5.2 Erweiterungsmöglichkeiten 55 5.3 Schlussbemerkung 57 Anhang V Vorgehensweise der Literaturrecherchen V Verwendete Computerkonfiguration IX Beispiele für Dateien X Beispiel für Detailausgabe von Simian X Beispiel für Detailausgabe von CCFinderX XI Beispiel für aggregierte Daten XII Abbildungsverzeichnis XIII Tabellenverzeichnis XIV Programmtextverzeichnis XV Abkürzungsverzeichnis XVI Literaturverzeichnis XVII Eidesstattliche Erklärung XXIII

Durch Redundanz im Quellcode kommt es zur Einschränkung wichtiger Faktoren wie der Lesbarkeit oder Wartbarkeit des Codes. Damit einhergehend kann Fehlverhalten im Programmablauf entstehen, wenn Code-Fragmente gezielt dupliziert werden, anstatt sie wiederzuverwenden. Für die frühzeitige Erkennung solcher Probleme ist es daher nötig, die Redundanz in ihren verschiedenen Formen aufzuschlüsseln. Das Ziel dieser Arbeit war es zu untersuchen, wodurch sich diese Formen beziehungsweise Arten der Redundanz unterscheiden, wie diese zusammenhängen und auf welche Weise man Redundanz mit dem Begriff Code-Clone zusammenführen kann. Zu diesem Zweck wurde eine Literaturstudie durchgeführt, um den aktuellen Forschungsstand zu erfassen. Dabei wurden neben der Redundanz auch die Themen Code-Clones und Ähnlichkeit betrachtet. Die Ergebnisse der Literaturstudie wurden anhand der Arten der Redundanz gegliedert und durch Code-Clone-Beispiele verdeutlicht. Die Literaturstudie ergab, dass Redundanz vorwiegend durch Duplikation von Code- Fragmenten entsteht, wodurch sich mithilfe von Code-Clones ein Großteil der Redundanz abbilden lässt. Des Weiteren sind die Arten der Redundanz nicht disjunkt, wodurch sich eine hundertprozentige Untergliederung nicht durchführen lässt.:Gliederung AbbildungsverzeichnisI Quellcode-Listing 1. Einleitung 1.1 Motivation 1.2 Zielstellung 1.3 Aufbau der Arbeit 2. Definitionen 3.Vorgehen 3.1Methodisches Vorgehen 3.2 Planung 3.3 Selektion 3.4 Extraktion 3.5 Ausführung 4. Ergebnisse 4.1 Negative Software Redundanz 4.2 Textuelle Redundanzen 4.3 Funktionelle Redundanz 4.4 Boilerplate-Code 4.5 Entstehungsgrund-basierte Redundanzen 4.5.1 Gezwungene Redundanz 4.5.2 Zufällige Redundanz 4.6 Abgrenzung der Redundanzarten voneinander 5. Fazit 6. Ausblick Quellen

Porcine reproductive and respiratory syndrome virus (PRRSV) is arguably the most economically-important swine pathogen. As the emergences of novel virulent strains of PRRSV continue to occur worldwide, rapid vaccine development is the key for effective control of ongoing PRRSV outbreaks. With the availability of the PRRSV reverse genetics systems, rapid vaccine development against PRRSV through the manipulation of the reverse genetics becomes feasible. To facilitate the vaccine development effort and study of PRRSV genes, we first established a DNA-launched infectious clone of the passage 14 PRRSV strain VR2385, pIR-VR2385-CA, and identified a spontaneous 435-bp deletion in the nsp2 gene. To characterize the biological and pathological significance of this nsp2 deletion, we restored deleted nsp2 sequence back to pIR-VR2385-CA and constructed another clone pIR-VR2385-R. VR2385-CA and VR2385-R were successfully rescued in vitro. The results from this study indicates that the spontaneous nsp2 deletion plays a role for enhanced PRRSV replication in vitro but has no significant effect on the pathogenicity of the virus. With the availability of the DNA-launched infectious clone of PRRSV, we successfully applied the molecular breeding approach to rapidly attenuate PRRSV. The GP5 envelope genes of 7 genetically divergent PRRSV strains and the GP5-M genes of 6 different PRRSV strains were molecularly bred. DS722 with shuffled GP5 genes and DS5M3 with shuffled GP5-M genes, were successfully rescued in vitro and shown to be attenuated both in vitro and in vivo. Furthermore, DS722, but not DS5M3, still elicit similar protection against PRRSV challenge as its parental virus. This study reveals a unique approach through DNA shuffling of viral envelope genes to attenuate a positive-strand RNA virus. We subsequently utilized the novel synthetic attenuated virus engineering (SAVE) approach to attenuate PRRSV. The GP5 and nsp9 genes of PRRSV were codon-pair deoptimized with the aid of a computer algorithm. SAVE5 and SAVE9 with deoptimized GP5 gene and SAVE9 with deoptimized nsp9 gene, were successfully rescued and shown to be attenuated in vitro. An in vivo pathogenicity study indicated the attenuation of SAVE5 virus in vivo. The results have important implications for rapid vaccine development against PRRSV and other important viruses. / Ph. D.

Reusing code can expedite software creation, analysis and exploration of data. Expediency can be particularly valuable for users of computational notebooks, where duplication allows them to quickly test hypotheses and iterate over data, without creating code from scratch. In this thesis, I’ll explore the topic of code duplication and the behaviour of code reuse for Jupyter notebooks; quantifying and describing snippets of code and explore potential barriers for reuse. As part of this thesis I conducted two studies into Jupyter notebooks use. In my first study, I mined GitHub repositories, quantifying and describing code duplicates contained within repositories that contained at least one Jupyter notebook. For my second study, I conducted an observational user study using a contextual inquiry, where my participants solved specific tasks using notebooks, while I observed and took notes. The work in this thesis can be categorized as exploratory, since both my studies were aimed at generating hypotheses for which further studies can build upon. My contributions with this thesis is two-fold: a thorough description of code duplicates contained within GitHub repositories and an exploration of the behaviour behind code reuse in Jupyter notebooks. It is my desire that others can build upon this work to provide new tools, addressing some of the issues outlined in this thesis. / Graduate

The use of F1 hybrids for commercial production of such cross-pollinated crops as corn, sorghum, sugar beets, onions, and pearl millet suggests the feasibility of using this technique for alfalfa. Production of F1 hybrids of commercial value is dependent on the use of breeding material expressing good combining ability. In order to obtain precise estimates of combining ability for quantitative characters in alfalfa, it is necessary to produce all possible single crosses among a number of parents. The single cross seed required is difficult to obtain due to the vegetative reproduction and isolation required; and, subsequently, limited testing of this type has been conducted in alfalfa. Testing breeding material for combining ability based on seed production has been more limited than testing based on forage yield or various other measurements. In this experiment a diallel crossing system was used to test the general and specific combining ability of five alfalfa clones previously selected for good general combining ability. The report is based on first-year data of a three-year study, and the results are subject to errors which may occur due to variability inherent in the year of establishment. This is especially true for conclusions based on seed production. However, first-year data should be valid for such characteristics as flower color and seedling height. The analysis of seed production and seedling height is designed to measure the relative amount of general and specific combining ability of the cones involved. Reciprocals of the single crosses were evaluated for flower color, seedling height, and seed yield to check if reciprocal cross progeny give equal performance.

Constraint satisfaction problems (CSPs) form a large class of decision problems that con- tains numerous classical problems like the satisfiability problem for propositional formulas and the graph colourability problem. Feder and Vardi [52] gave the following logical for- malization of the class of CSPs: every finite relational structure A, the template, gives rise to the decision problem of determining whether there exists a homomorphism from a finite input structure B to A. In their seminal paper, Feder and Vardi recognised that CSPs had a particular status in the landscape of computational complexity: despite the generality of these problems, it seemed impossible to construct NP-intermediate problems `a la Ladner [72] within this class. The authors thus conjectured that the class of CSPs satisfies a complexity dichotomy , i.e., that every CSP is solvable in polynomial time or is NP-complete. The Feder-Vardi dichotomy conjecture was the motivation of an intensive line of research over the last two decades. Some of the landmarks of this research are the confirmation of the conjecture for special classes of templates, e.g., for the class of undi- rected graphs [55], for the class of smooth digraphs [5], and for templates with at most three elements [43, 84]. Finally, after being open for 25 years, Bulatov [44] and Zhuk [87] independently proved that the conjecture of Feder and Vardi indeed holds. The success of the research program on the Feder-Vardi conjecture is based on the con- nection between constraint satisfaction problems and universal algebra. In their seminal paper, Feder and Vardi described polynomial-time algorithms for CSPs whose template satisfies some closure properties. These closure properties are properties of the polymor- phism clone of the template and similar properties were later used to provide tractability or hardness criteria [61, 62]. Shortly thereafter, Bulatov, Jeavons, and Krokhin [46] proved that the complexity of the CSP depends only on the equational properties of the poly- morphism clone of the template. They proved that trivial equational properties imply hardness of the CSP, and conjectured that the CSP is solvable in polynomial time if the polymorphism clone of the template satisfies some nontrivial equation. It is this conjecture that Bulatov and Zhuk finally proved, relying on recent developments in universal algebra. As a by-product of the fact that the delineation between polynomial-time tractability and NP-hardness can be stated algebraically, we also obtain that the meta-problem for finite- domain CSPs is decidable. That is, there exists an algorithm that, given a finite relational structure A as input, decides the complexity of the CSP of A.

Network satisfaction problems (NSPs) for finite relation algebras are computational decision problems, studied intensively since the 1990s. The major open research challenge in this field is to understand which of these problems are solvable by polynomial-time algorithms. Since there are known examples of undecidable NSPs of finite relation algebras it is advisable to restrict the scope of such a classification attempt to well-behaved subclasses of relation algebras. The class of relation algebras with a normal representation is such a well-behaved subclass. Many well-known examples of relation algebras, such as the Point Algebra, RCC5, and Allen’s Interval Algebra admit a normal representation. The great advantage of finite relation algebras with normal representations is that their NSP is essentially the same as a constraint satisfaction problem (CSP). For a relational structure B the problem CSP(B) is the computational problem to decide whether a given finite relational structure C has a homomorphism to B. The study of CSPs has a long and rich history, culminating for the time being in the celebrated proofs of the Feder-Vardi dichotomy conjecture. Bulatov and Zhuk independently proved that for every finite structure B the problem CSP(B) is in P or NP-complete. Both proofs rely on the universal-algebraic approach, a powerful theory that connects algebraic properties of structures B with complexity results for the decision problems CSP(B). Our contributions to the field are divided into three parts. Firstly, we provide two algebraic criteria for NP-hardness of NSPs. Our second result is a complete classification of the complexity of NSPs for symmetric relation algebras with a flexible atom; these problems are in P or NP-complete. Our result is obtained via a decidable condition on the relation algebra which implies polynomial-time tractability of the NSP. As a third contribution we prove that for a large class of NSPs, non-hardness implies that the problems can even be solved by Datalog programs, unless P = NP. This result can be used to strengthen the dichotomy result for NSPs of symmetric relation algebras with a flexible atom: every such problem can be solved by a Datalog program or is NP-complete. Our proof relies equally on known results and new observations in the algebraic analysis of finite structures. The CSPs that emerge from NSPs are typically of the form CSP(B) for an infinite structure B and therefore do not fall into the scope of the dichotomy result for finite structures. In this thesis we study NSPs of finite relation algebras with normal representations by the universal algebraic methods which were developed for the study of finite and infinite-domain CSPs. We additionally make use of model theory and a Ramsey-type result of Nešetril and Rödl. Our contributions to the field are divided into three parts. Firstly, we provide two algebraic criteria for NP-hardness of NSPs. Our second result is a complete classification of the complexity of NSPs for symmetric relation algebras with a flexible atom; these problems are in P or NP-complete. Our result is obtained via a decidable condition on the relation algebra which implies polynomial-time tractability of the NSP. As a third contribution we prove that for a large class of NSPs the containment in P implies that the problems can even be solved by Datalog programs, unless P = NP. As a third contribution we prove that for a large class of NSPs, non-hardness implies that the problems can even be solved by Datalog programs, unless P = NP. This result can be used to strengthen the dichotomy result for NSPs of symmetric relation algebras with a flexible atom: every such problem can be solved by a Datalog program or is NP-complete. Our proof relies equally on known results and new observations in the algebraic analysis of finite structures.