In this thesis, inference of biological networks from in vivo data generated by perturbation experiments is considered, i.e. deduction of causal interactions that exist among the observed variables. Knowledge of such regulatory influences is essential in biology. A system property–interampatteness–is introduced that explains why the variation in existing gene expression data is concentrated to a few “characteristic modes” or “eigengenes”, and why previously inferred models have a large number of false positive and false negative links. An interampatte system is characterized by strong INTERactions enabling simultaneous AMPlification and ATTEnuation of different signals and we show that perturbation of individual state variables, e.g. genes, typically leads to ill-conditioned data with both characteristic and weak modes. The weak modes are typically dominated by measurement noise due to poor excitation and their existence hampers network reconstruction. The excitation problem is solved by iterative design of correlated multi-gene perturbation experiments that counteract the intrinsic signal attenuation of the system. The next perturbation should be designed such that the expected response practically spans an additional dimension of the state space. The proposed design is numerically demonstrated for the Snf1 signalling pathway in S. cerevisiae. The impact of unperturbed and unobserved latent state variables, that exist in any real biological system, on the inferred network and required set-up of the experiments for network inference is analysed. Their existence implies that a subnetwork of pseudo-direct causal regulatory influences, accounting for all environmental effects, in general is inferred. In principle, the number of latent states and different paths between the nodes of the network can be estimated, but their identity cannot be determined unless they are observed or perturbed directly. Network inference is recognized as a variable/model selection problem and solved by considering all possible models of a specified class that can explain the data at a desired significance level, and by classifying only the links present in all of these models as existing. As shown, these links can be determined without any parameter estimation by reformulating the variable selection problem as a robust rank problem. Solution of the rank problem enable assignment of confidence to individual interactions, without resorting to any approximation or asymptotic results. This is demonstrated by reverse engineering of the synthetic IRMA gene regulatory network from published data. A previously unknown activation of transcription of SWI5 by CBF1 in the IRMA strain of S. cerevisiae is proven to exist, which serves to illustrate that even the accumulated knowledge of well studied genes is incomplete. / Denna avhandling behandlar inferens av biologiskanätverk från in vivo data genererat genom störningsexperiment, d.v.s. bestämning av kausala kopplingar som existerar mellan de observerade variablerna. Kunskap om dessa regulatoriska influenser är väsentlig för biologisk förståelse. En system egenskap—förstärksvagning—introduceras. Denna förklarar varför variationen i existerande genexpressionsdata är koncentrerat till några få ”karakteristiska moder” eller ”egengener” och varför de modeller som konstruerats innan innehåller många falska positiva och falska negativa linkar. Ett system med förstärksvagning karakteriseras av starka kopplingar som möjliggör simultan FÖRSTÄRKning och förSVAGNING av olika signaler. Vi demonstrerar att störning av individuella tillståndsvariabler, t.ex. gener, typiskt leder till illakonditionerat data med både karakteristiska och svaga moder. De svaga moderna domineras typiskt av mätbrus p.g.a. dålig excitering och försvårar rekonstruktion av nätverket. Excitationsproblemet löses med iterativdesign av experiment där korrelerade störningar i multipla gener motverkar systemets inneboende försvagning av signaller. Följande störning bör designas så att det förväntade svaret praktiskt spänner ytterligare en dimension av tillståndsrummet. Den föreslagna designen demonstreras numeriskt för Snf1 signalleringsvägen i S. cerevisiae. Påverkan av ostörda och icke observerade latenta tillståndsvariabler, som existerar i varje verkligt biologiskt system, på konstruerade nätverk och planeringen av experiment för nätverksinferens analyseras. Existens av dessa tillståndsvariabler innebär att delnätverk med pseudo-direkta regulatoriska influenser, som kompenserar för miljöeffekter, generellt bestäms. I princip så kan antalet latenta tillstånd och alternativa vägar mellan noder i nätverket bestämmas, men deras identitet kan ej bestämmas om de inte direkt observeras eller störs. Nätverksinferens behandlas som ett variabel-/modelselektionsproblem och löses genom att undersöka alla modeller inom en vald klass som kan förklara datat på den önskade signifikansnivån, samt klassificera endast linkar som är närvarande i alla dessa modeller som existerande. Dessa linkar kan bestämmas utan estimering av parametrar genom att skriva om variabelselektionsproblemet som ett robustrangproblem. Lösning av rangproblemet möjliggör att statistisk konfidens kan tillskrivas individuella linkar utan approximationer eller asymptotiska betraktningar. Detta demonstreras genom rekonstruktion av det syntetiska IRMA genreglernätverket från publicerat data. En tidigare okänd aktivering av transkription av SWI5 av CBF1 i IRMA stammen av S. cerevisiae bevisas. Detta illustrerar att t.o.m. den ackumulerade kunskapen om välstuderade gener är ofullständig. / <p>QC 20130508</p>

In this thesis, we design, develop and implement parallel algorithms for irregular problems on heterogeneous multi-core architectures. Irregular problems exhibit random and unpredictable memory access patterns, poor spatial locality and input dependent control flow. Heterogeneous multi-core processors vary in: clock frequency, power dissipation, programming model (MIMD vs. SIMD), memory design and computing units, scalar versus vector units. The heterogeneity of the processors makes designing efficient parallel algorithms for irregular problems on heterogeneous multicore processors challenging. Techniques of mapping tasks or data on traditional parallel computers can not be used as is on heterogeneous multi-core processors due to the varying hardware. In an attempt to understand the efficiency of futuristic heterogeneous multi-core architectures on applications we study several computation and bandwidth oriented irregular problems on one heterogeneous multi-core architecture, the IBM Cell Broadband Engine (Cell BE). The Cell BE consists of a general processor and eight specialized processors and addresses vector/data-level parallelism and instruction-level parallelism simultaneously. Through these studies on the Cell BE, we provide some discussions and insight on the performance of the applications on heterogeneous multi-core architectures. Verifying these experimental results require some performance modeling. Due to the diversity of heterogeneous multi-core architectures, theoretical performance models used for homogeneous multi-core architectures do not provide accurate results. Therefore, in this thesis we propose an analytical performance prediction model that considers the multitude architectural features of heterogeneous multi-cores (such as DMA transfers, number of instructions and operations, the processor frequency and DMA bandwidth). We show that the execution time from our prediction model is comparable to the execution time of the experimental results for a complex medical imaging application.

In this thesis, we design, develop and implement parallel algorithms for irregular problems on heterogeneous multi-core architectures. Irregular problems exhibit random and unpredictable memory access patterns, poor spatial locality and input dependent control flow. Heterogeneous multi-core processors vary in: clock frequency, power dissipation, programming model (MIMD vs. SIMD), memory design and computing units, scalar versus vector units. The heterogeneity of the processors makes designing efficient parallel algorithms for irregular problems on heterogeneous multicore processors challenging. Techniques of mapping tasks or data on traditional parallel computers can not be used as is on heterogeneous multi-core processors due to the varying hardware. In an attempt to understand the efficiency of futuristic heterogeneous multi-core architectures on applications we study several computation and bandwidth oriented irregular problems on one heterogeneous multi-core architecture, the IBM Cell Broadband Engine (Cell BE). The Cell BE consists of a general processor and eight specialized processors and addresses vector/data-level parallelism and instruction-level parallelism simultaneously. Through these studies on the Cell BE, we provide some discussions and insight on the performance of the applications on heterogeneous multi-core architectures. Verifying these experimental results require some performance modeling. Due to the diversity of heterogeneous multi-core architectures, theoretical performance models used for homogeneous multi-core architectures do not provide accurate results. Therefore, in this thesis we propose an analytical performance prediction model that considers the multitude architectural features of heterogeneous multi-cores (such as DMA transfers, number of instructions and operations, the processor frequency and DMA bandwidth). We show that the execution time from our prediction model is comparable to the execution time of the experimental results for a complex medical imaging application.

Ferramentas de geoinformação possuem grande aplicabilidade na compreensão e no mapeamento de deslizamentos. Considerando-se a importância dos componentes do relevo e da cobertura do solo neste processo, torna-se essencial o estabelecimento de metodologias para a síntese de informações do relevo e para a identificação de cicatrizes de deslizamento, de maneira a facilitar o monitoramento de áreas de risco. O objetivo desta Tese é propor metodologias de processamento digital de imagens para o mapeamento e identificação de cicatrizes de deslizamento próximo a rodovias. Um deslizamento de grande porte com várias consequências econômicas, ocorrido no ano de 1999, às margens da Rodovia Anchieta, na bacia hidrográfica do Rio Pilões foi utilizado como área de estudo deste trabalho. Utilizando dados gratuitos, mapas de cobertura do solo e de compartimentação do relevo foram gerados e analisados conjuntamente para a identificação das áreas de potenciais cicatrizes na região das Rodovias Anchieta e Imigrantes. A análise do relevo foi realizada utilizando técnicas de classificação baseada em objeto. A identificação de áreas de cicatrizes de deslizamento foi realizada através da avaliação de duas estratégias metodológicas: uma utilizando o algoritmo de classificação supervisionada SVM (Support Vector Machine) aplicado ao índice de vegetação NDVI (Normalized Difference Vegetation Index) e outra que utilizando combinação entre diferentes classificadores para a composição de uma classificação final. Os resultados obtidos para o mapeamento do relevo mostraram que a metodologia proposta possui grande potencial para a descrição de feições do relevo, com maior nível de detalhamento, facilitando a identificação de áreas com grande potencial de ocorrência de deslizamentos. Ambas as metodologias de identificação de cicatrizes de deslizamento apresentaram bons resultados, sendo que a combinação entre os algoritmos SVM, Redes Neurais e Máxima Verossimilhança apresentou o resultado mais adequado com os objetivos do trabalho, atingindo erro de omissão inferior a 10% para a classe de deslizamento. A combinação dos dois produtos permitiu a análise e identificação de diversas áreas de potenciais cicatrizes de deslizamento associadas à rodovias na região de estudo. A metodologia proposta possui ampla replicabilidade, podendo ser utilizada para análises de risco associadas a assentamentos urbanos, empreendimentos lineares e para o planejamento territorial e ambiental. / Geoinformation tools have great applicability in understanding and mapping landslides. Considering the significance of releif components and land cover in this process, it is essential the establishment of methods for the synthesis of the relief information and identification landslides, aiming to facilitate areas risk monitoring. The objective of this Dissertation is to propose digital image processing methodologies for map and identify landslide near to highways. A large landslide with several economic consequences was used as a study area of this work, occurred in 1999, near the Highway Anchieta, in Piloes river basin. Using free data, land cover and relief subdivsion maps were generated and intersected to identify areas of potential landslides in the region of Highways Anchieta and Imigrantes. The relief analysis was performed using based on object classification techniques. The identification of the landslide was performed by evaluating two methodological strategies: one using the supervised classification algorithm SVM (Support Vector Machine) applied to the NDVI vegetation index (Normalized Difference Vegetation Index) and another using combination of different classifiers for the composition of a final classification. The results obtained for relief mapping showed that the proposed method has great potential for the description of the relief features, with greater detail, facilitating the identification of areas with high potential for occurrence of landslides. Both landslides identification methodologies showed good results, and the combination of SVM, Neural Network and Maximum Likelihood algorithms presented the most appropriate result, reaching omission error of less than 10% for the landslide class. The combination of the two products allowed the analysis and identification of several areas of potential landslide scars associated with roads in the study area. The proposed methodology has extensive replication and can be used for risk analysis associated with urban settlements, linear infrastructures and the territorial and environmental planning.

DNA methylation is involved in various biological phenomena, and its dysregulation has been demonstrated as being correlated with a number of human disease processes, including cancers, autism, and autoimmune, mental health and neuro-degenerative ones. It has become important and useful in characterising and modelling these biological phenomena in or-der to understand the mechanism of such occurrences, in relation to both health and disease. An attempt has previously been made to map DNA methylation across human tissues, however, the means of distinguishing between methylated, unmethylated and differentially-methylated groups using DNA sequence features remains unclear. The aim of this study is therefore to: firstly, investigate DNA methylation classes and predict these based on DNA sequence features; secondly, to further identify methylation-associated DNA sequence features, and distinguish methylation differences between males and females in relation to both healthy and diseased, sta-tuses. This research is conducted in relation to three samples within nine biological feature sub-sets extracted from DNA sequence patterns (Human genome database). Two samples contain classes (methylated, unmethy-lated and differentially-methylated) within a total of 642 samples with 3,809 attributes driven from four human chromosomes, i.e. chromosomes 6, 20, 21 and 22, and the third sample contains all human chromosomes, which encompasses 1628 individuals, and then 1,505 CpG loci (features) were extracted by using Hierarchical clustering (a process Heatmap), along with pair correlation distance and then applied feature selection methods. From this analysis, author extract 47 features associated with gender and age, with 17 revealing significant methylation differences between males and females. Methylation classes prediction were applied a K-nearest Neighbour classifier, combined with a ten-fold cross- validation, since to some data were severely imbalanced (i.e., existed in sub-classes), and it has been established that direct analysis in machine-learning is biased towards the majority class. Hence, author propose a Modified- Leave-One-Out (MLOO) cross-validation and AdaBoost methods to tackle these issues, with the aim of compositing a balanced outcome and limiting the bias in-terference from inter-differences of the classes involved, which has provided potential predictive accuracies between 75% and 100%, based on the DNA sequence context.

No description available.

The aim of this project was to improve upon a toolfor strategy synthesis for multi-agent games of imperfect informationagainst nature. Another objective was to compare the toolwith the original tool we improved upon and the Strategic ModelChecker (SMC). For the strategy synthesis, an existing extensionfor expanding the games called the Multi-Agent Knowledge-Based Subset Construction was used. The construction creates anew knowledge-based game where strategies can be tested. Thestrategies were synthesized for the individual agents and thenjoint profiles of the individual strategies were tested to see ifthey were winning.Four different algorithms for going through the game graphswere tested against the other existing tools. The new andimproved tool was faster at synthesizing a strategy than both theold tool and the SMC for almost all games tested. Although forthe games where the new tool is out-performed, results indicateit to be due to a combination of chance and how the games areperceived by the tools. No algorithm or tool proved to be thebest performing for all games. / Syftet med detta projekt var att förbättra ettexisterande verktyg för att syntetisera strategier för fleragentspelav imperfect information mot naturen. Därefter också jämföraverktyget med original verktyget och med ett verktyg somheter the strategic model checker (SMC). För syntetiseringenav strategier användes ett existerande verktyg för att expanderaspel, som kallas Multi-Agent Knowledge-Based Subset Construction.Konstruktionen skapar ett kunskapsbaserat spel därstrategierna kan bli testade. Strategierna syntetiserades för deenskilda agenterna och därefter skapades en sammansatt profilav strategier, som då testades för att se om det var en vinnandestrategi.Fyra olika algoritmer för att gå igenom spelgrafen testadesoch jämfördes med de andra verktygen. Det nya och förbättradeverktyget var snabbare att syntetisera en strategi än både detgamla verktyget och SMC verktyget för nästan alla spel somtestades. Fast, för spelen då nya verktyget inte var snabbast så indikerar resultaten på att detta är p.g.a. en kombination avslump och hur spelen ses på av verktygen. Ingen algoritm ellerverktyg visade sig vara det snabbaste för samtliga spel. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm

Strategies in games have since long been of interestto humans, mainly to beat our friends in games such as Chessor Monopoly, but also to model real world scenarios. Thesestrategies are often difficult to find, even more so if the playerslack important information about the current state of the game.Pursuit-Evasion games are a type of games that can be usedto model police chasing criminals, autonomous car collisionavoidance systems and many other scenarios. It is therefore ofinterest to find effective strategies in these scenarios.This bachelor thesis project examined Pursuit-Evasion gamesof imperfect information on grids where a number of pursuerswork together to capture a number of evaders whose locationsare unknown. A set of knowledge-based strategies, one of theminspired by the Knowledge Based Subset Construction, wereexplored and analyzed. The strategies were compared againsteach other and against both an optimal strategy where thepursuers always were aware of the evaders whereabouts anda reference strategy where the pursuers moved randomly.The constructed strategies proved to be efficient in comparisonto the reference and in cases even close to the optimal strategyin efficiency. / Strategier i spel har sedan länge varit avintresse för oss människor, framförallt för att vinna mot vårakompisar i spel som Schack eller Monopol, men också för attmodellera verkliga scenarion. Dessa strategier är ofta svåra attlista ut, och ännu svårare då spelarna saknar viktig informationom spelets nuvarande läge. Pursuit-Evasion är en klass av spelsom kan användas för att modellera polisjakter eller kollisionsundvikandesystem i autonoma bilar för att nämna några. Detligger därför i vårt intresse att finna effektiva strategier i dessascenarion.Detta kandidatsexamensarbete studerade Pursuit-Evasion spelav imperfekt information på rutnät där ett antal så kallade pursuerssamarbetade för att fånga ett antal så kallade evaders varspostioner var okända. En kunskaps-representation utformadesoch en mängd kunskaps-baserade strategier, en inspirerad avmetoden Knowledge Based Subset Construction, utforskades ochtestades. De olika strategierna jämfördes mot varandra och motbåde en optimal strategi då pursuers hade all kunskap om varalla evaders befann sig och en referensstrategi då pursuers rördesig slumpmässigt.De utformade strategierna visade sig vara effektiva i jämförelsemed referensen och i vissa fall till och med nära den optimalastrategin i effektivitet. / Kandidatexjobb i elektroteknik 2021, KTH, Stockholm

主題-評論結構(topic-comment)在主題顯著(topic prominent)的語言(如中文)扮演十分重要的角色,尤其是在描述第二語言學習者的中介語時特別重要．但是有關研究,對於中國學生在學習英文時產生的中介語,並沒有對主題-評論結構提供全面且確切的描述．本研究旨在探討中國學生學習英文時所產生的中介語之主題-評論結構, 運用三種測驗來引出中介語—文法判定測驗, 引導寫作測驗, 及翻譯測驗．受試者包含台灣區域位於台北的三所國中挑選的94位國二生,以國一期末考英文成績分為三組．此外,並於政大語視中心挑選14位以英語為母語的外籍生作為本研究的控制組．本研究探討的四種主題-評論結構是由中英文主題結構對比中所產生的, 分別為主題省略(topic drop), 主題移前(topicalization), 主題置左(left-dislocation), 及雙主詞結構(double-subject construction)．本研究所運用的中介語之理論架構是參考三種第二外語習得理論所發展出來的, 分別為第一語言影響(L1 influence), 普遍語法(universal grammar)的存在, 以及附屬集合理論(the Subset Principle)． 研究結果顯示, 第一語言轉換(L1 transfer)在所有程度的學生的中介語當中都十分普遍, 但是普遍語法只有在程度最高的學生的中介語較為明顯．因此本研究推論中介語系統內部運作過程包含三階段, 開始為第一語言轉換, 接著是第一語言轉換及普遍語法並存, 最後階段為普遍語法． / The role that the topic-comment structure plays in a topic prominent language such as Chinese is very important when it comes to SLA learners’ interlanguage. However, the related research has not provided a comprehensive framework in describing topic structures of Chinese EFL learners’ interlanguage. The purpose of this study is to analyze the topic structures in Chinese EFL learners’ interlanguage elicited by three tasks—the grammaticality judgment task, the guided writing task, and the translation task. The subjects include 94 junior high school students chosen from three separate schools in Taipei, Taiwan, and they were divided into three proficiency levels. In addition, 14 native speakers from the language center of NCCU served as the control group. This study investigated four topic structures—topic drop, topicalization, left-dislocation, and double-subject construction—which were determined by a comparative study of Chinese and English topic structures. The current theoretical framework of interlanguage operation is developed from three SLA perspectives—L1 influence, the existence of universal grammar (UG), and the subset principle. Results indicated that L1 transfer was prevalent in all proficiency levels but UG was only obvious in the most advanced level. It was thus inferred that the internal operation of interlanguage system should include three stages—first L1 transfer, then L1 transfer and UG, and finally UG.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.