Computational Techniques for Haplotype Inference and for Local Alignment Significance

This thesis which consists of an introduction and four peer-reviewed original publications studies the problems of haplotype inference (haplotyping) and local alignment significance. The problems studied here belong to the broad area of bioinformatics and computational biology. The presented solutions are computationally fast and accurate, which makes them practical in high-throughput sequence data analysis. Haplotype inference is a computational problem where the goal is to estimate haplotypes from a sample of genotypes as accurately as possible. This problem is important as the direct measurement of haplotypes is difficult, whereas the genotypes are easier to quantify. Haplotypes are the key-players when studying for example the genetic causes of diseases. In this thesis, three methods are presented for the haplotype inference problem referred to as HaploParser, HIT, and BACH. HaploParser is based on a combinatorial mosaic model and hierarchical parsing that together mimic recombinations and point-mutations in a biologically plausible way. In this mosaic model, the current population is assumed to be evolved from a small founder population. Thus, the haplotypes of the current population are recombinations of the (implicit) founder haplotypes with some point--mutations. HIT (Haplotype Inference Technique) uses a hidden Markov model for haplotypes and efficient algorithms are presented to learn this model from genotype data. The model structure of HIT is analogous to the mosaic model of HaploParser with founder haplotypes. Therefore, it can be seen as a probabilistic model of recombinations and point-mutations. BACH (Bayesian Context-based Haplotyping) utilizes a context tree weighting algorithm to efficiently sum over all variable-length Markov chains to evaluate the posterior probability of a haplotype configuration. Algorithms are presented that find haplotype configurations with high posterior probability. BACH is the most accurate method presented in this thesis and has comparable performance to the best available software for haplotype inference. Local alignment significance is a computational problem where one is interested in whether the local similarities in two sequences are due to the fact that the sequences are related or just by chance. Similarity of sequences is measured by their best local alignment score and from that, a p-value is computed. This p-value is the probability of picking two sequences from the null model that have as good or better best local alignment score. Local alignment significance is used routinely for example in homology searches. In this thesis, a general framework is sketched that allows one to compute a tight upper bound for the p-value of a local pairwise alignment score. Unlike the previous methods, the presented framework is not affeced by so-called edge-effects and can handle gaps (deletions and insertions) without troublesome sampling and curve fitting.

Construction of a global map of human gene expression : the process, tools and analysis

This thesis studies human gene expression space using high throughput gene expression data from DNA microarrays. In molecular biology, high throughput techniques allow numerical measurements of expression of tens of thousands of genes simultaneously. In a single study, this data is traditionally obtained from a limited number of sample types with a small number of replicates. For organism-wide analysis, this data has been largely unavailable and the global structure of human transcriptome has remained unknown. This thesis introduces a human transcriptome map of different biological entities and analysis of its general structure. The map is constructed from gene expression data from the two largest public microarray data repositories, GEO and ArrayExpress. The creation of this map contributed to the development of ArrayExpress by identifying and retrofitting the previously unusable and missing data and by improving the access to its data. It also contributed to creation of several new tools for microarray data manipulation and establishment of data exchange between GEO and ArrayExpress. The data integration for the global map required creation of a new large ontology of human cell types, disease states, organism parts and cell lines. The ontology was used in a new text mining and decision tree based method for automatic conversion of human readable free text microarray data annotations into categorised format. The data comparability and minimisation of the systematic measurement errors that are characteristic to each lab- oratory in this large cross-laboratories integrated dataset, was ensured by computation of a range of microarray data quality metrics and exclusion of incomparable data. The structure of a global map of human gene expression was then explored by principal component analysis and hierarchical clustering using heuristics and help from another purpose built sample ontology. A preface and motivation to the construction and analysis of a global map of human gene expression is given by analysis of two microarray datasets of human malignant melanoma. The analysis of these sets incorporate indirect comparison of statistical methods for finding differentially expressed genes and point to the need to study gene expression on a global level.

Identifying Meaningful Places

Place identification refers to the process of analyzing sensor data in order to detect places, i.e., spatial areas that are linked with activities and associated with meanings. Place information can be used, e.g., to provide awareness cues in applications that support social interactions, to provide personalized and location-sensitive information to the user, and to support mobile user studies by providing cues about the situations the study participant has encountered. Regularities in human movement patterns make it possible to detect personally meaningful places by analyzing location traces of a user. This thesis focuses on providing system level support for place identification, as well as on algorithmic issues related to the place identification process. The move from location to place requires interactions between location sensing technologies (e.g., GPS or GSM positioning), algorithms that identify places from location data and applications and services that utilize place information. These interactions can be facilitated using a mobile platform, i.e., an application or framework that runs on a mobile phone. For the purposes of this thesis, mobile platforms automate data capture and processing and provide means for disseminating data to applications and other system components. The first contribution of the thesis is BeTelGeuse, a freely available, open source mobile platform that supports multiple runtime environments. The actual place identification process can be understood as a data analysis task where the goal is to analyze (location) measurements and to identify areas that are meaningful to the user. The second contribution of the thesis is the Dirichlet Process Clustering (DPCluster) algorithm, a novel place identification algorithm. The performance of the DPCluster algorithm is evaluated using twelve different datasets that have been collected by different users, at different locations and over different periods of time. As part of the evaluation we compare the DPCluster algorithm against other state-of-the-art place identification algorithms. The results indicate that the DPCluster algorithm provides improved generalization performance against spatial and temporal variations in location measurements.

TCP Performance in Heterogeneous Wireless Networks

The TCP protocol is used by most Internet applications today, including the recent mobile wireless terminals that use TCP for their World-Wide Web, E-mail and other traffic. The recent wireless network technologies, such as GPRS, are known to cause delay spikes in packet transfer. This causes unnecessary TCP retransmission timeouts. This dissertation proposes a mechanism, Forward RTO-Recovery (F-RTO) for detecting the unnecessary TCP retransmission timeouts and thus allow TCP to take appropriate follow-up actions. We analyze a Linux F-RTO implementation in various network scenarios and investigate different alternatives to the basic algorithm. The second part of this dissertation is focused on quickly adapting the TCP's transmission rate when the underlying link characteristics change suddenly. This can happen, for example, due to vertical hand-offs between GPRS and WLAN wireless technologies. We investigate the Quick-Start algorithm that, in collaboration with the network routers, aims to quickly probe the available bandwidth on a network path, and allow TCP's congestion control algorithms to use that information. By extensive simulations we study the different router algorithms and parameters for Quick-Start, and discuss the challenges Quick-Start faces in the current Internet. We also study the performance of Quick-Start when applied to vertical hand-offs between different wireless link technologies.

Exploring privacy for ubiquitous computing: Tools, methods and experiments

Ubiquitous computing is about making computers and computerized artefacts a pervasive part of our everyday lifes, bringing more and more activities into the realm of information. The computationalization, informationalization of everyday activities increases not only our reach, efficiency and capabilities but also the amount and kinds of data gathered about us and our activities. In this thesis, I explore how information systems can be constructed so that they handle this personal data in a reasonable manner. The thesis provides two kinds of results: on one hand, tools and methods for both the construction as well as the evaluation of ubiquitous and mobile systems---on the other hand an evaluation of the privacy aspects of a ubiquitous social awareness system. The work emphasises real-world experiments as the most important way to study privacy. Additionally, the state of current information systems as regards data protection is studied. The tools and methods in this thesis consist of three distinct contributions. An algorithm for locationing in cellular networks is proposed that does not require the location information to be revealed beyond the user's terminal. A prototyping platform for the creation of context-aware ubiquitous applications called ContextPhone is described and released as open source. Finally, a set of methodological findings for the use of smartphones in social scientific field research is reported. A central contribution of this thesis are the pragmatic tools that allow other researchers to carry out experiments. The evaluation of the ubiquitous social awareness application ContextContacts covers both the usage of the system in general as well as an analysis of privacy implications. The usage of the system is analyzed in the light of how users make inferences of others based on real-time contextual cues mediated by the system, based on several long-term field studies. The analysis of privacy implications draws together the social psychological theory of self-presentation and research in privacy for ubiquitous computing, deriving a set of design guidelines for such systems. The main findings from these studies can be summarized as follows: The fact that ubiquitous computing systems gather more data about users can be used to not only study the use of such systems in an effort to create better systems but in general to study phenomena previously unstudied, such as the dynamic change of social networks. Systems that let people create new ways of presenting themselves to others can be fun for the users---but the self-presentation requires several thoughtful design decisions that allow the manipulation of the image mediated by the system. Finally, the growing amount of computational resources available to the users can be used to allow them to use the data themselves, rather than just being passive subjects of data gathering.

Mining Cell Transition Data

Cell transition data is obtained from a cellular phone that switches its current serving cell tower. The data consists of a sequence of transition events, which are pairs of cell identifiers and transition times. The focus of this thesis is applying data mining methods to such data, developing new algorithms, and extracting knowledge that will be a solid foundation on which to build location-aware applications. In addition to a thorough exploration of the features of the data, the tools and methods developed in this thesis provide solutions to three distinct research problems. First, we develop clustering algorithms that produce a reliable mapping between cell transitions and physical locations observed by users of mobile devices. The main clustering algorithm operates in online fashion, and we consider also a number of offline clustering methods for comparison. Second, we define the concept of significant locations, known as bases, and give an online algorithm for determining them. Finally, we consider the task of predicting the movement of the user, based on historical data. We develop a prediction algorithm that considers paths of movement in their entirety, instead of just the most recent movement history. All of the presented methods are evaluated with a significant body of real cell transition data, collected from about one hundred different individuals. The algorithms developed in this thesis are designed to be implemented on a mobile device, and require no extra hardware sensors or network infrastructure. By not relying on external services and keeping the user information as much as possible on the user s own personal device, we avoid privacy issues and let the users control the disclosure of their location information.

Mobiilitunnistamisen hyödyt ja mahdollisuudet Helsingin yliopistossa

Employees and students in University of Helsinki use various services which require authentication. Some of these services require strong authentication. Traditionally this has been realized by meeting in person and presenting an official identification card. Some of these online services can be automatized by implementing existing techniques for strong authentication. Currently strong authentication is implemented by VETUMA-service. Mobile authentication is interesting alternative method. The purpose of this paper is to study the Mobile Signature Service technology and to find out the benefits and possibilities of its use for mobile authentication in University of Helsinki. Mobile authentication is suitable method for implementing strong authentication and for signing documents digitally. Mobile authentication can be used in many different ways in Helsinki university.

Intranet Alman käytettävyydestä

Usability testing is a productive and reliable method for evaluating the usability of software. Planning and implementing the test and analyzing its results is typically considered time-consuming, whereas applying usability methods in general is considered difficult. Because of this, usability testing is often priorized lower than more concrete issues in software engineering projects. Intranet Alma is a web service, users of which consist of students and personnel of the University of Helsinki. Alma was published in 2004 at the opening ceremony of the university. It has 45 000 users, and it replaces several former university network services. In this thesis, the usability of intranet Alma is evaluated with usability testing. The testing method applied has been lightened to make its taking into use as easy as possible. In the test, six students each tried to solve nine test tasks with Alma. As a result concrete usability problems were described in the final test report. Goal-orientation was given less importance in the applied usability testing. In addition, the system was tested only with test users from the largest user group. Usability test found general usability problems that occurred no matter the task or the user. However, further evaluation needs to be done: in addition to the general usability problems, there are task-dependent problems, solving of which requires thorough gathering of users goals. In the basic structure and central functionality of Alma, for example in navigation, there are serious and often repeating usability problems. It would be of interest to verify the designed user interface solutions to these problems before taking them into use. In the long run, the goals of the users, that the software is planned to support, are worth gathering, and the software development should be based on these goals.

Määrittelyvaiheen vaatimusten vaikutukset käyttöliittymään

Tässä työssä tutkitaan, miten vaatimusmäärittelydokumenttiin kirjatut vaatimukset kiinnittävät myöhemmissä ohjelmistokehitysprosessin vaiheissa tehtäviä käyttöliittymäratkaisuja. Lisäksi tutkitaan, jääkö käyttöliittymästä puuttumaan todellisissa käyttötilanteissa tarvittavia toimintoja, kun vaatimusmäärittely toteutetaan perinteisen vesiputousmallin mukaisesti. Tutkimuksessa tarkastellaan kahden Helsingin yliopiston ohjelmistotuotantoprojekti-kurssilla toteutetun opiskelijaprojektin tuotoksia. Tutkimuksessa selvitetään oppilaiden tuottamien käyttöliittymien keskeisimmät käyttöliittymäongelmat simulointitestaamalla käyttöliittymät. Testauksessa simuloitiin ohjelmiston kolme keskeisintä käyttötilannetta, jotka selvitettiin tekemällä kontekstuaalinen käyttäjähaastattelu yhdelle opettajatuutorille. Tämän jälkeen etsittiin, löytyvätkö ongelmien syyt ryhmien vaatimusmäärittelydokumentteihin kirjatuista käyttötapauskuvauksista tai muista vaatimuksista. Tämän työn keskeisimpinä tuloksina selvisi, että käyttötapaukset sitoivat aina toiminnon ja sen toteutuksen käyttöliittymässä, mutta vain pieni osa niistä kiinnitti käyttöliittymäratkaisuja haitallisesti. Vakavien tehokkuusongelmien ja järjestelmästä puuttuvan toiminnallisuuden syyt kuitenkin olivat nimenomaan vaatimusmäärittelydokumentin käyttötapauksissa. Muut vaatimukset kiinnittivät toimintoja niin korkealla tasolla, ettei niistä muodostunut ongelmallisia käyttöliittymäratkaisuja. Lisäksi havaittiin, että molemmista vaatimusmäärittelyistä oli jäänyt pois sellaisia toimintoja, joita oltaisiin tarvittu käyttötilanteen suorittamiseen tehokkaasti. Vaikuttaisi siltä, että vaatimusmäärittelyvaiheessa ei ole saatu selville käyttäjän todellisia käyttötilanteita, minkä seurauksena vaatimuksista on jäänyt pois oleellisia toimintoja.

Aspektiohjelmointi ja hauraat liitoskohtamääritykset

Läpileikkaava näkökulma on tietokoneohjelman toteutukseen liittyvä vaatimus, jota ei voida toteuttaa käytetyllä ohjelmointikielellä omaan ohjelmayksikköön, vaan sen toteutus hajaantuu useisiin ohjelmayksiköihin. Aspektiohjelmointi on uusi ohjelmointiparadigma, jolla läpileikkaava näkökulma voidaan toteuttaa omaan ohjelmayksikköön, aspektiin. Aspekti kapseloi näkökulman toteutuksen neuvon ja liitoskohtamäärityksen avulla. Neuvo sisältää näkökulman toteuttavan ohjelmakoodin ja liitoskohtamääritys valitsee ne ohjelman liitoskohdat, joihin ohjelmakoodi liitetään. Nykyisillä aspektikielillä voidaan valita liitoskohtia pääasiassa niiden syntaktisten ominaisuuksien, kuten nimen ja sijainnin, perusteella. Syntaksiin sidoksissa olevat liitoskohtamääritykset ovat hauraita, sillä ohjelmaan tehdyt muutokset voivat rikkoa syntaksista riippuvia liitoskohtamäärityksiä, vaikka itse liitoskohtamäärityksiin ei tehtäisi muutoksia. Tätä ongelmaa kutsutaan hauraan liitoskohtamäärityksen ongelmaksi. Ongelma on merkittävä, koska hauraat liitoskohtamääritykset vaikeuttavat ohjelman kehitettävyyttä ja ylläpidettävyyttä. Tässä tutkielmassa perehdytään hauraan liitoskohtamäärityksen ongelmaan ja siihen esitettyihin ratkaisuihin. Tutkielmassa näytetään, että ongelmaan ei ole tällä hetkellä kunnollista ratkaisua.

Avoimet julkaisuarkistot ja niiden tekniikka

Open Access -liike pyrkii vapauttamaan tieteellisen tiedon kaupallisuuden rajoitteista edesauttamalla artikkeleiden rinnakkaisversioiden avointa ja esteetöntä verkkotallennusta. Sen mahdollistamiseksi verkkoon perustetaan julkaisuarkistoja, joiden toiminta-ajatuksena on säilöä taustayhteisönsä tieteellinen tuotanto avoimesti ja keskitetysti yhteen paikkaan. Avoimen lähdekoodin arkistosovellukset jakavat sisältönsä OAI-protokollan avulla ja muodostavat näin globaalin virtuaalisen tietoverkon. Suurten tietomäärien käsittelyssä on huomioitava erityisesti kuvailutiedon rooli tehokkaiden hakujen toteuttamisessa sekä tiedon yksilöiminen verkossa erilaisten pysyvien tunnisteiden, kuten Handle:n tai URN:n avulla. Tieteellisen tiedon avoimella saatavuudella on merkittävä vaikutus myös oppimisen näkökulmasta. Julkaisuarkistot tarjoavat oppimateriaalin lisäksi uusia mahdollisuuksia julkaisukanavan ja oppimisymp äristön integroimiseen. Työssä esitellään avoimen saatavuuden keskeisiä teemoja sekä sen käytännön toteutusta varten kehitettyjä teknisiä ratkaisuja. Näiden pohjalta toteutetaan Meilahden kampuksen avoin julkaisuarkisto. Työssä pohditaan myös julkaisuarkistojen soveltuvuutta oppimisprosessin tukemiseen tutkivan- ja sulautuvan oppimisen viitekehyksessä. ACM Computing Classification System (CCS): H.3 [INFORMATION STORAGE AND RETRIEVAL], H.3.7 [Digital Libraries], H.3.3 [Information Search and Retrieval], H.3.5 [Online Information Services], K.3 [COMPUTERS AND EDUCATION], K.3.1 [Computer Uses in Education]

Viivesietoisten verkkojen nykytila ja tulevaisuuden haasteet

Delay and disruption tolerant networks (DTNs) are computer networks where round trip delays and error rates are high and disconnections frequent. Examples of these extreme networks are space communications, sensor networks, connecting rural villages to the Internet and even interconnecting commodity portable wireless devices and mobile phones. Basic elements of delay tolerant networks are a store-and-forward message transfer resembling traditional mail delivery, an opportunistic and intermittent routing, and an extensible cross-region resource naming service. Individual nodes of the network take an active part in routing the traffic and provide in-network data storage for application data that flows through the network. Application architecture for delay tolerant networks differs also from those used in traditional networks. It has become feasible to design applications that are network-aware and opportunistic, taking an advantage of different network connection speeds and capabilities. This might change some of the basic paradigms of network application design. DTN protocols will also support in designing applications which depend on processes to be persistent over reboots and power failures. DTN protocols could also be applicable to traditional networks in cases where high tolerance to delays or errors would be desired. It is apparent that challenged networks also challenge the traditional strictly layered model of network application design. This thesis provides an extensive introduction to delay tolerant networking concepts and applications. Most attention is given to challenging problems of routing and application architecture. Finally, future prospects of DTN applications and implementations are envisioned through recent research results and an interview with an active researcher of DTN networks.

Rakenteiset sanakirjat

Sanakirjat ovat rakenteisia tekstejä. Sana-artikkeleissa on nähtävissä selvästi erotettavissa olevia rakenneosia. Painetun sanakirjan muuntaminen rakenteiseen muotoon ei kuitenkaan ole aivan suoraviivaista. Tässä tutkielmassa kerrotaan sanakirjan rakennekuvauksen määrittelyn ja painetun sanakirjan rakenteistuksen ongelmista. Esimerkkinä käytetään Kotimaisten kielten tutkimuskeskuksessa (Kotus) kirjoitettavan Suomen murteiden sanakirjan (SMS) rakenteistusprojektia ja sen yhteydessä määriteltyä rakennekuvausta. SMS:n rakennekuvausta verrataan kielitieteellisten aineistojen koodaamisessa yleisesti käytetyn Text Encoding Initiative -suosituksen sekä uuden ISO 1951:2007 -sanakirjastandardin määrittelemiin rakennekuvauksiin. Muuntamista testataan käytännössä kirjoittamalla XSL-muunnosskripti, joka muuntaa SMS:n aineiston ISOstandardimuotoon. Muunnosprosessin voi todeta olleen hyödyllinen, koska sen aikana paljastui ongelmia sekä SMS:n rakennekuvauksessa että itse standardin määrittelyssä. Tulosten avulla SMS:n koodausta voidaan kehittää edelleen. Lopuksi tarkastellaan standardien käytöstä yleisesti saatavia hyötyjä ja mahdollisuuksia soveltaa niitä Kotuksen sanakirjatyöhön.

Tietokannan hallintajärjestelmän optimointi flash-muistia varten

Viime aikoina yleistyneet flash-muistiin perustuvat tallennusvälineet ovat monessa suhteessa kiintolevyä parempia. Flash-muistissa on kuitenkin useita erityispiirteitä, jotka vaikeuttavat sen käyttöönottoa tietokantajärjestelmässä. Flash-muistissa kirjoittaminen on hitaampaa kuin lukeminen. Erityisesti hajanaisten sivujen päivittäminen on hidasta. Hajaluku flash-muistista on huomattavasti nopeampaa kuin kiintolevyltä. Näiden erityispiirteiden vuoksi tietokannan hallintajärjestelmä on optimoitava erikseen flash-muistia varten. Tässä optimoinnissa lähes kaikki tietokannan hallintajärjestelmän osa-alueet on toteutettava uudelleen flash-muistin näkökulmasta. Flash-muistin nopean hajaluvun ansiosta relaatioiden tiedot voidaan sijoitella flash-muistiin vapaammin kuin kiintolevylle. Yleisin tietokannoissa käytetty hakemistorakenne B+-puu ei toimi tehokkaasti flash-muistissa hajapäivitysten suuren määrän vuoksi. Flashmuistia varten on kehitetty useita B+-puun muunnelmia, joissa hajapäivitysten määrää on onnistuttu vähentämään. Puskurin hallintaa voidaan optimoida flash-muistia varten vähentämällä hitaiden kirjoitusten määrää nopeiden lukujen määrän kustannuksella sekä muuttamalla hitaita hajakirjoituksia nopeammiksi peräkkäisten sivujen kirjoituksiksi. B.3 (hardware, memory structures) H.2.2 (database management, physical design)

Kenttätutkimusaineiston hyödyntäminen käyttöliittymäsuunnittelussa

Tässä työssä arvioidaan kenttätutkimusaineiston hyödyntämisen etuja käyttöliittymäsuunnittelussa. Tulokset perustuvat kahden samasta ohjelmasta eri tavalla suunnitellun käyttöliittymän arviointiin. Käytettävissä on aikaisemmin suunniteltu käyttöliittymä ja tässä työssä suunniteltava uusi käyttöliittymä, jonka suunnittelussa hyödynnetään kenttätutkimuksesta saatua aineistoa. Aluksi tässä työssä käydään läpi kenttätutkimuksen perusteet, tehdään suunnitelma kenttätutkimuksesta ja käydään tekemässä käyttäjien työtiloissa kenttätutkimusta kontekstuaalisen haastattelun menetelmän mukaisesti. Seuraavaksi käydään läpi käyttöliittymäsuunnittelun teoriaa, esitellään tässä työssä käytettävä GDDsuunnittelumenetelmä ja tehdään sen tarvitsemat tavoitepohjaiset käyttötapaukset kenttätutkimusaineiston pohjalta. Tämän jälkeen simuloidaan uusi käyttöliittymä käyttäen ainoastaan kenttätutkimuksesta saatua aineistoa. Lopuksi simuloitua ja aiemmin suunniteltua käyttöliittymää arvioidaan oikeilla käyttäjillä läpikäyntipalavereissa ja analysoidaan tulokset. Tuloksissa osoitetaan miten todellisten käyttötilanteiden simulointi tuottaa erilaisia käyttöliittymäratkaisuja verrattuna toimintojen toteuttamiseen. Käyttöliittymäratkaisujen ongelmien pohjalta todetaan, että on hyvin tärkeää ymmärtää käyttäjien todellinen työprosessi. Pelkästään kaikkien tarpeellisten toimintojen toteuttaminen ei takaa hyvää käyttöliittymää. On tärkeää miten toiminnot ja tietosisältö on aseteltu käyttöliittymään. Simuloinnissa ne suunnitellaan käyttöliittymään käyttäjien työn kannalta paremmassa järjestyksessä. Tämä nopeuttaa käyttäjien työskentelyä ja parantaa opittavuutta, koska tietoa ja toiminnallisuutta ei tarvitse etsiä käyttöliittymästä. Tekstin lopussa arvioidaan tässä työssä käytettyjen menetelmien soveltamista käytäntöön käyttöliittymäsuunnitteluprosessiin käytetyn ajan ja läpikäyntipalaverien analyysin perusteella.