Hepatitis B virus (HBV), the prototype member of the family Hepadnaviridae, is hepatotropic and replicates by reverse transcription. HBV is responsible for the chronic infection of more than 240 million people worldwide, of which 65 million reside in Africa. The nine HBV genotypes (A to I) identified to date, are geographically distributed and exhibit different clinical manifestations and treatment responses. The term occult HBV infection (OBI) refers to a HBV infection in which HBV surface antigen (HBsAg) cannot be detected by conventional serological assays as has been defined by the Taormina expert panel. . HBV and human immune deficiency virus (HIV) are both endemic in many parts of the world and share common transmission routes. Worldwide, 10% of those infected with HIV are also chronically infected with HBV. HIV co-infection has been shown to be a risk factor for the development of OBI in individuals infected with HBV. The aim of this study was to characterize, at the molecular level, HBV from mono-infected and HBV/HIV co-infected individuals in Sudan The objectives of this study were the systematic and comparative analysis of HBV genotype D sequences, available in the public databases; the molecular characterization of HBV from mono-infected Sudanese liver disease patients and from HBV/HIV co-infected Sudanese patients; and the development and testing of bioinformatics tools to explore HBV sequence data generated using ultradeep pyrosequencing (UDPS) and comparison of UDPS results with those obtained from cloning based sequencing (CBS). All available complete genomes of genotype D of HBV from the GenBank database were analyzed. The intra-group divergence of the subgenotypes ranged from 0.8% + 0.5 for subgenotype D6 to 3.0% + 0.3 for subgenotype D8. Phylogenetic analysis of genotype D showed separation into six distinct clusters (subgenotypes D1, D2, D3/D6, D4, D5 and D7/D8), with good bootstrap support. The mean intergroup divergence between subgenotype D3 and subgenotype D6 was 2.6%, falling below the accepted threshold of 4% required to define a subgenotype. This suggests that subgenotypes D3 and D6 are the same subgenotype because they also share signature amino acids. Furthermore, subgenotype D8 is a genotype D/E recombinant, which clusters with subgenotype D7. This analysis provided an update on the classification of the subgenotypes of genotype D of HBV. Although HBsAg seroprevalence in Sudan, a central-African country, is greater than 8%, the only sequencing data for HBV, available prior to our study, was from asymptomatic blood donors, where genotype E predominates, followed by genotype D and subgenotype A2. Ninety-nine HBV-positive liver disease patients were enrolled in our study, including: 15 with hepatocellular carcinoma (HCC), 42 with cirrhosis, 30 asymptomatic carriers, 7 with acute hepatitis and 5 with chronic hepatitis. The surface and basic core promoter/precore (BCP/PC) regions, and the complete genome of HBV were sequenced. Eighty-two percent of the samples from HBV mono-infected liver disease patients were genotyped. Fifty-nine percent were infected with genotype D (74% D1, 10% D2, 3% D3 and 13% D6), 30% with genotype E, 8.5% with genotype A and 2.5% with a genotype D/E recombinant. Patients infected with genotype E had a higher frequency of HBeAg-positivity (29.2%) and higher viral loads compared to patients infected with genotype D. BCP/PC region mutations, including the G1896A mutation, seen in 37% of the HBeAg-negative individuals, could account for the HBeAg-negativity. A total of 358 Sudanese HIV-positive patients were enrolled. HBsAg was detected in 11.7% of the participants, indicating chronic HBV infection. HBV DNA was detected in 26.8% of the participants: 11.7% were HBsAg positive (overt infection) and the remaining 15.1% were HBsAg-negative (OBI). Fifty serum samples from the HBV/HIV DNA-positive co-infected participants were selected for genomic analysis of HBV. Of these, the HBV genotype of 37 was determined. The genotype distribution of HBV isolates from the HBV/HIV co-infected participants did not differ significantly from those from the HBV mono-infected patients: genotype D (46%), E (21.6%), A (18.9%) and a D/E recombinant (13.5%). Compared to the HBV isolates from mono-infected liver disease patients, the frequency of the D/E recombinant and genotype A was higher in HBV/HIV co-infected patients, as was the intragroup divergence of genotype E. No difference in BCP/PC mutations affecting HBeAg expression at the transcriptional and translational levels between genotype D and E was observed. The following mutations could account for the HBsAg-negativity: sM133T, sE164G, sV168G and sS174N. No primary drug resistance mutations were found. Two online bioinformatics tools, the ―Deep Threshold Tool (DDT)‖ and the ―Rosetta Tool‖, were built to analyze data generated from UDPS and CBS of the BCP/PC region of four Sudanese serum samples, infected with either genotype D or E of HBV, from HBeAgpositive and HBeAg negative patients. A total of 10952 reads were generated by UDPS on the 454 GS Junior platform. The Threshold was calculated using DDT based on probability of error of 0.5%. In total, 39 unique mutations were identified by UDPS, of which 25 were nonsynonymous. The ratio of nucleotide substitutions between isolates from HBeAg-negative and HBeAg-positive patients was 3.5:1. From the sequences analyzed, compared to genotype E isolates, genotype D isolates showed greater variation in the X, BCP/PC/C regions. Only 18 of the 39 positions identified by UDPS were detected by CBS. Using the specific criteria, that have been suggested previously, to define genotypes/subgenotypes of HBV, we determined that genotype D has six and not eight subgenotypes. The importance of HBV genotypes in clinical consequences of infection and response to antiviral treatment has led us to characterize HBV genotypes circulating in Sudan. HBV mono-infected patients and HBV/HIV co-infected individuals, were mainly infected with genotype D or E. HBV mono-infected patients, infected with genotype E, had higher HBeAg-positivity and higher viral loads than those infected with genotype D. The ratio of genotype A to non- A, as well as the genotype E intra-group divergence were higher in HBV/HIV co-infected individuals compared to HBV mono-infected individuals. OBI was found in 15.1% HBV/HIV co-infected patients and its clinical relevance remains to be determined. In order to overcome the limitations of Sanger sequencing, which include its high cost and inability to detect minor populations in quasispecies, next generation sequencing techniques have been developed. It was demonstrated that correct analysis of UDPS data required appropriate curation of read data, in order to clean the data and eliminate artefacts and that the appropriate consensus (reference) sequence should be used in order to identify variants correctly. CBS detected fewer than 50% of the substitutions detected by UDPS. This new technology may allow the detection of minor variants between the different genotypes of HBV and provide biomarkers for the prediction of clinical manifestation of HBV and response to antiviral therapy.

Listeria monocytogenes and Campylobacter spp. are bacteria that sometimes can cause severe illness in humans. Both can be found as contaminants in food that has been produced, stored or prepared improperly, which is why it is important to ensure that the handling of food is done correctly. The National Food Agency (Livsmedelsverket) is the Swedish authority responsible for food safety. One important task is to, in collaboration with other authorities, track and prevent food-related disease outbreaks. For this purpose bacterial samples are regularly collected from border control, at food production facilities and retail as well as from suspected food items and drinking water during outbreaks, and epidemiological analyses are employed to determine the type of bacteria present and whether they can be linked to a common source. One part of these epidemiological analyses involve bioinformatic analyses of the bacterial DNA. This includes determination of sequence type and serotype, as well as calculations of similarities between samples. Such analyses require data processing in several different steps which are usually performed by a bioinformatician using different computer programs. Currently the National Food Agency outsources most of these analyses to other authorities and companies, and the purpose of this project was to develop a pipeline that would allow for these analyses to be performed in-house. The result was a pipeline named BacIL - Bacterial Identification and Linkage which has been developed to automatically perform sequence typing, serotyping and SNP-analysis of Listeria monocytogenes as well as sequence typing and SNP-analysis of Campylobacter jejuni, C. coli and C. lari. The result of the SNP-analysisis is used to create clusters which can be used to identify related samples. The pipeline decreases the number of programs that have to be manually started from more than ten to two.

In this report, we rank possible protein biomarkers based on different criteria for use in Olink Proteomics’ protein panels. We started off with a list compiled through the Human Plasma Proteome Project (HPPP) and have in different ways used this to obtain the final results. To complete this task we compared the list with Olink’s and its competitors’ protein catalogs, identified diseases beyond Olink’s coverage and the proteins linked with these. We also created a scoring system used to fa- cilitate detection of good biomarkers. From this, we have concluded that Olink should focus on proteins that the competitors have in their catalogs and proteins that can be found in many pathways and are linked with many diseases. From each of the methods used, we have been able to identify a number of proteins that we recommend Olink to investigate further.

轉錄因子(TF) 和轉錄因子結合位點(TFBS) 之間的結合(binding) 是重要的生物信息學課題。高清晰度(長度<10 )的結合核心(binding core) 是從昂貴和費時的三維結構實驗中發現的。因此，我們希望開發一種以序列為基礎的高效計算方法，提供高信心的結合核心作為實驗對象，以提高三維結構實驗的效率。雖然現有很多基於序列的motif辨認算法，但很少有直接針對關聯TF和TFBS的結合核心的。在不使用任何三維結構的結合核心下，最近我們應用了關聯規則挖掘方法於低分辨率的(TF長度>490) 結合序列準確地發掘出高清晰度結合核心，然而，這種方法有幾個缺點。在這篇論文中，我們正式地定義了使用關聯規則挖掘預測蛋白質-脫氧核糖核酸(DNA) 結合核心的問題和開發了一個以樹為基礎的算法以克服前一種方法的缺點。 / 目前的關聯規則挖掘方法在這個問題上只能解決確切的序列，而最近的近似方法並沒有採用任何正式的模型，並且受限於實驗已知的序列。由於生物的基因突變是常見的，因此我們進一步定義開採近似的蛋白質-DNA序列結合核心的問題，並延伸該算法至預測近似的蛋白質-DNA結合核心。真實數據的實驗結果中表明了在該算法在預測新的TF-TFBS結合核心中的性能和適用性。最後，我們提出、測試並討論了多種減少雜訊以提高結果質量的方案。其中，當最小支持度(minimumsupport) 的限制定得低時，統計檢驗能有效地從結果中删除雜訊。 / The studies of protein-DNA bindings between transcription fac-tors (TFs) and transcription factor binding sites (TFBSs) are important bioinformatics topics. Currently, high-resolution (length < 10) TF-TFBS binding cores are discovered by expensive and time-consuming 3D structure experiments. Thus, we are motivated to develop a cheap and efficient sequence-based computational method for providing testable novel binding cores with high condence to accelerate the experiments. Although there are abundant sequence-based motif discovery algorithms, few directly address associating both TF and TFBS core motifs, which are both veriable on 3D structures. Recent association rule mining approaches on low-resolution binding sequences (TF length > 490) are shown promising in identifying accurate binding cores without using any 3D structures, however, the approach has several drawbacks. In this thesis, the problem of predicting protein-DNA binding cores using association rule mining is formally dened and a novel tree-based algorithm is developed to overcome the disadvantages of the previous approach. / While the previous association rule mining method on this problem addresses exact sequences only, the most recent ad hoc method for approximation does not establish any formal model and is limited by experimentally known patterns. As biological mutations are common, it is desirable to formally extend the exact model into an approximate one. Thus, we further formalize the problem of mining approximate protein-DNA association rules from sequence data and extend the proposed algorithm to predict approximate protein-DNA binding cores. Experimental results on real data show the performance and applicability of the proposed algorithm in predicting novel TF-TFBS binding cores. Finally, several methods for reducing noise and thus improving the quality of the mined rules are proposed and discussed. Particularly, statistical tests give impressive result on removing noise when the minimum support threshold is small. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Wong, Po Yuen. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 126-136). / Abstracts also in Chinese. / Abstract --- p.i / Acknowledgement --- p.vi / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Predicting Protein-DNA Binding Cores --- p.1 / Chapter 1.2 --- Contributions --- p.3 / Chapter 1.3 --- Thesis Outline --- p.4 / Chapter 2 --- Background --- p.6 / Chapter 2.1 --- Biological Background --- p.7 / Chapter 2.1.1 --- The Central Dogma of Molecular Biology --- p.7 / Chapter 2.1.2 --- Transcriptional Regulation --- p.10 / Chapter 2.1.3 --- Experiments on studying TF-TFBS bindings --- p.12 / Chapter 2.2 --- Computational Background --- p.13 / Chapter 2.2.1 --- Motif Discovery --- p.13 / Chapter 2.2.2 --- Association Rule Mining --- p.14 / Chapter 2.2.3 --- Frequent Pattern Mining --- p.16 / Chapter 2.3 --- TF-TFBS Binding Rule Mining in Bioinformatics --- p.17 / Chapter 3 --- Mining TF-TFBS Rules --- p.23 / Chapter 3.1 --- Introduction --- p.24 / Chapter 3.2 --- Problem Definition --- p.25 / Chapter 3.3 --- Frequent Sequence Tree (FS-Tree) --- p.31 / Chapter 3.3.1 --- Semantic of FS-Tree --- p.31 / Chapter 3.3.2 --- Construction of FS-Tree --- p.34 / Chapter 3.4 --- The algorithm --- p.40 / Chapter 3.4.1 --- Correctness --- p.42 / Chapter 3.5 --- Results --- p.44 / Chapter 3.5.1 --- Performance --- p.45 / Chapter 3.5.2 --- Verification using 3D-Structures --- p.53 / Chapter 3.6 --- Discussion and Conclusion --- p.58 / Chapter 3.6.1 --- Parameters Setting --- p.59 / Chapter 3.6.2 --- Deduplication --- p.60 / Chapter 4 --- Extension to Approximate TF-TFBS Rules --- p.63 / Chapter 4.1 --- Introduction --- p.65 / Chapter 4.2 --- Problem Definition --- p.66 / Chapter 4.3 --- Frequent Sequence Class Tree --- p.74 / Chapter 4.4 --- The extended algorithm --- p.82 / Chapter 4.4.1 --- Correctness --- p.87 / Chapter 4.5 --- Results --- p.89 / Chapter 4.5.1 --- Performance --- p.89 / Chapter 4.5.2 --- Verification using PDB --- p.94 / Chapter 4.6 --- Discussion and Conclusion --- p.100 / Chapter 5 --- Noise Reducing Methods --- p.102 / Chapter 5.1 --- Introduction --- p.103 / Chapter 5.2 --- Reducing Noise within a TFBS Group --- p.104 / Chapter 5.2.1 --- Using Exact Count Threshold --- p.106 / Chapter 5.2.2 --- Using Minimum Support --- p.108 / Chapter 5.2.3 --- Using Minimum Approximate Support --- p.110 / Chapter 5.3 --- Reducing Noise using Statistical Test --- p.112 / Chapter 5.3.1 --- A Simple Model --- p.114 / Chapter 5.3.2 --- Statistical Model with Transactions --- p.116 / Chapter 5.4 --- Discussion and Conclusion --- p.120 / Chapter 6 --- Conclusion --- p.121 / Chapter 6.1 --- Conclusion --- p.121 / Chapter 6.2 --- Future Work --- p.123 / Bibliography --- p.126 / Chapter A --- Publications --- p.137 / Chapter A.1 --- Publications --- p.137

<p>In this thesis I have studied the RNA molecule and its function and characteristics in the regulation of gene expression. I have focused on two events that are important for the regulation of the transcriptome: Translational regulation through micro RNAs; and RNA editing through adenosine deaminations.</p><p>Micro RNAs (miRNAs) are ~22 nucleotides long RNA molecules that by semi complementarity bind to untranslated regions of a target messenger RNA (mRNA). The interaction manifests through an RNA/protein complex and act mainly by repressing translation of the target mRNA. I have shown that a pre-cursor miRNA molecule have significantly different information content of sequential composition of the two arms of the pre-cursor hairpin. I have also shown that sequential composition differs between species.</p><p>Selective adenosine to inosine (A-to-I) RNA editing is a post-transcriptional process whereby highly specific adenosines in a (pre-)messenger transcript are deaminated to inosines. The deamination is carried out by the ADAR family of proteins and require a specific sequential and structural landscape for target recognition. Only a handful of messenger substrates have been found to be site selectively edited in mammals. Still, most of these editing events have an impact on neurotransmission in the brain.</p><p>In order to find novel substrates for A-to-I editing, an experimental setup was made to extract RNA targets of the ADAR2 enzyme. In concert with this experimental approach, I have constructed a computational screen to predict specific positions prone to A-to-I editing.</p><p>Further, I have analyzed editing in the mouse brain at four different developmental stages by 454 amplicon sequencing. With high resolution, I present data supporting a general developmental regulation of A-to-I editing. I also present data of coupled editing events on single RNA transcripts suggesting an A-to-I editing mechanism that involve ADAR dimers to act in concert. A different editing pattern is seen for the serotonin receptor 5-ht2c.</p>

In this thesis I have studied the RNA molecule and its function and characteristics in the regulation of gene expression. I have focused on two events that are important for the regulation of the transcriptome: Translational regulation through micro RNAs; and RNA editing through adenosine deaminations. Micro RNAs (miRNAs) are ~22 nucleotides long RNA molecules that by semi complementarity bind to untranslated regions of a target messenger RNA (mRNA). The interaction manifests through an RNA/protein complex and act mainly by repressing translation of the target mRNA. I have shown that a pre-cursor miRNA molecule have significantly different information content of sequential composition of the two arms of the pre-cursor hairpin. I have also shown that sequential composition differs between species. Selective adenosine to inosine (A-to-I) RNA editing is a post-transcriptional process whereby highly specific adenosines in a (pre-)messenger transcript are deaminated to inosines. The deamination is carried out by the ADAR family of proteins and require a specific sequential and structural landscape for target recognition. Only a handful of messenger substrates have been found to be site selectively edited in mammals. Still, most of these editing events have an impact on neurotransmission in the brain. In order to find novel substrates for A-to-I editing, an experimental setup was made to extract RNA targets of the ADAR2 enzyme. In concert with this experimental approach, I have constructed a computational screen to predict specific positions prone to A-to-I editing. Further, I have analyzed editing in the mouse brain at four different developmental stages by 454 amplicon sequencing. With high resolution, I present data supporting a general developmental regulation of A-to-I editing. I also present data of coupled editing events on single RNA transcripts suggesting an A-to-I editing mechanism that involve ADAR dimers to act in concert. A different editing pattern is seen for the serotonin receptor 5-ht2c.

To understand biology at a system level, I presented novel machine learning algorithms to reveal the underlying mechanisms of how genes and their products function in different biological levels in this thesis. Specifically, at sequence level, based on Kernel Support Vector Machines (SVMs), I proposed learned random-walk kernel and learned empirical-map kernel to identify protein remote homology solely based on sequence data, and I proposed a discriminative motif discovery algorithm to identify sequence motifs that characterize protein sequences' remote homology membership. The proposed approaches significantly outperform previous methods, especially on some challenging protein families. At expression and protein level, using hierarchical Bayesian graphical models, I developed the first high-throughput computational predictive model to filter sequence-based predictions of microRNA targets by incorporating the proteomic data of putative microRNA target genes, and I proposed another probabilistic model to explore the underlying mechanisms of microRNA regulation by combining the expression profile data of messenger RNAs and microRNAs. At cellular level, I further investigated how yeast genes manifest their functions in cell morphology by performing gene function prediction from the morphology data of yeast temperature-sensitive alleles. The developed prediction models enable biologists to choose some interesting yeast essential genes and study their predicted novel functions.

To understand biology at a system level, I presented novel machine learning algorithms to reveal the underlying mechanisms of how genes and their products function in different biological levels in this thesis. Specifically, at sequence level, based on Kernel Support Vector Machines (SVMs), I proposed learned random-walk kernel and learned empirical-map kernel to identify protein remote homology solely based on sequence data, and I proposed a discriminative motif discovery algorithm to identify sequence motifs that characterize protein sequences' remote homology membership. The proposed approaches significantly outperform previous methods, especially on some challenging protein families. At expression and protein level, using hierarchical Bayesian graphical models, I developed the first high-throughput computational predictive model to filter sequence-based predictions of microRNA targets by incorporating the proteomic data of putative microRNA target genes, and I proposed another probabilistic model to explore the underlying mechanisms of microRNA regulation by combining the expression profile data of messenger RNAs and microRNAs. At cellular level, I further investigated how yeast genes manifest their functions in cell morphology by performing gene function prediction from the morphology data of yeast temperature-sensitive alleles. The developed prediction models enable biologists to choose some interesting yeast essential genes and study their predicted novel functions.

In this thesis I present research in two fields: machine learning and computational biology. First, I develop new machine learning methods for graphical models that can be applied to protein problems. Then I apply graphical model algorithms to protein problems, obtaining improvements in protein structure prediction and protein structure alignment. First,in the machine learning work, I focus on a special kind of graphical model---conditional random fields (CRFs). Here, I present a new semi-supervised training procedure for CRFs that can be used to train sequence segmentors and labellers from a combination of labeled and unlabeled training data. Such learning algorithms can be applied to protein and gene name entity recognition problems. This work provides one of the first semi-supervised discriminative training methods for structured classification. Second, in my computational biology work, I focus mainly on protein problems. In particular, I first propose a tree decomposition method for solving the protein structure prediction and protein structure alignment problems. In so doing, I reveal why tree decomposition is a good method for many protein problems. Then, I propose a computational framework for detection of similar structures of a target protein with sparse NMR data, which can help to predict protein structure using experimental data. Finally, I propose a new machine learning approach---LS_Boost---to solve the protein fold recognition problem, which is one of the key steps in protein structure prediction. After a thorough comparison, the algorithm is proved to be both more accurate and more efficient than traditional z-Score method and other machine learning methods.

In this thesis I present research in two fields: machine learning and computational biology. First, I develop new machine learning methods for graphical models that can be applied to protein problems. Then I apply graphical model algorithms to protein problems, obtaining improvements in protein structure prediction and protein structure alignment. First,in the machine learning work, I focus on a special kind of graphical model---conditional random fields (CRFs). Here, I present a new semi-supervised training procedure for CRFs that can be used to train sequence segmentors and labellers from a combination of labeled and unlabeled training data. Such learning algorithms can be applied to protein and gene name entity recognition problems. This work provides one of the first semi-supervised discriminative training methods for structured classification. Second, in my computational biology work, I focus mainly on protein problems. In particular, I first propose a tree decomposition method for solving the protein structure prediction and protein structure alignment problems. In so doing, I reveal why tree decomposition is a good method for many protein problems. Then, I propose a computational framework for detection of similar structures of a target protein with sparse NMR data, which can help to predict protein structure using experimental data. Finally, I propose a new machine learning approach---LS_Boost---to solve the protein fold recognition problem, which is one of the key steps in protein structure prediction. After a thorough comparison, the algorithm is proved to be both more accurate and more efficient than traditional z-Score method and other machine learning methods.