Dissertations / Theses on the topic 'DNA sequences'

Thesis (M.S.)--University of Missouri-Columbia, 2005.
"May 2005" The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Includes bibliographical references.

An investigation into the presence of plasmids in Mycobacterium tuberculosis was conducted. No extrachromosomal DNA was found although some evidence for their presence were detected. Plasmid-related sequences were however found in the genomic DNA of M, tuberculosis. Isolation of plasmid-related sequences from a strain of M, tuberculosis resulted in two different DNA probes which showed high specificity for M, tuberculosis and related species. One of these probes gave banding patterns which suggest the presence of restriction fragment polymorphism in M, tuberculosis. The other probe gave banding patterns which were unique for each strain tested. The use of these probes for epidemiological studies is suggested. An E. coli plasmid, pIJ666, was successfully introduced into Mycobacterium smegmatis ATCC607 and stably maintained through several subcultures. One of the selective markers, a chloramphenicol resistance gene from Tn9, was efficiently expressed in M. smegmatis ATCC607. The development of a transformation system in M. smegmatis from this initial study is indicated.

Thesis (Ph. D.) -- University of Maryland, College Park, 2006.
Thesis research directed by: Applied Mathematics and Scientific Computation Program. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

Tandemly repeated tracts of DNA are a ubiquitous feature of eukaryote genomes. One class of tandem repeats, 'minisatellites', have been shown to be highly variable both in overall length and in the internal arrangement of variant versions of the repeating unit along the array. Consequently, both length and internal variation at these loci can be exploited to generate individual-specific profiles of use in forensic science and the establishment of family relationships. Recently it has been demonstrated that short dinucleotide repeats, or 'microsatellites', and other simple tandem repeat arrays can also show length variation. This work describes the isolation and characterization of simple tandem repeat arrays, and their application in a forensic science case. The evolutionary persistence of variability at tandem repeat loci is also explored. Simple tandem repeats isolated were frequently associated with other tandem repeats and interspersed repetitive elements, a phenomenon previously described for minisatellites and perhaps indicative that certain genomic regions show relaxed fidelity in the maintenance of large-scale DNA structure, allowing tandem array expansion and retroposon insertion. Although variability is low relative to minisatellites, microsatellites, owing to limited length, can readily be amplified from highly degraded DNA using the polymerase chain reaction. Consequently it was possible to identify positively the skeletal remains of a murder victim by comparing microsatellite profiles of the skeleton with those of the presumptive parents. Comparative studies of microsatellite and minisatellite loci between man and other primates indicate that in evolutionary terms, the variable state is reasonably persistent at microsatellite loci, whereas highly variable minisatellites show extreme evolutionary transience. Such transience was also demonstrated for two large 'midisatellite' loci, suggesting that highly variable tandem repeat loci are extremely unstable and transient, whereas lower variability leads to evolutionary persistence of the variable state.

We develop a new class of computationally feasible stochastic models for statistical analysis of genetic sequence evolution and inference of properties of the underlying substitution processes in the context of maximum likelihood framework. Existing models for evolution of protein coding sequences allow site to site variation in non-synonymous substitution rates, but assume that the rate of synonymous substitutions is constant for all sites. New models provide a rigorous statistical framework for testing the hypothesis of synonymous rate constancy, and enable a host of data exploration and analysis tools. For several indicative data sets, the constancy assumption is shown to be violated, and some possible explanations are given. We also present an algorithm for improving efficiency of maximum likelihood evaluations, and discuss HyPhy--a user friendly and publicly distributed software implementation of our methods.

In this thesis you should find an optimal approach to index and retriev DNA sequences. As part of the task you should develop an algorithm that is fast, and accurate enough to find relevant sequences. The result will be evaluated based on speed, scalability and search efficiency (e.g. Precision and Recall). The approach should be implemented in a Java-based prototype which will be a "proof-of-the-concept".

We address the problem of the DNA sequences developing a "dynamical" method based on the assumption that the statistical properties of DNA paths are determined by the joint action of two processes, one deterministic, with long-range correlations, and the other random and delta correlated. The generator of the deterministic evolution is a nonlinear map, belonging to a class of maps recently tailored to mimic the processes of weak chaos responsible for the birth of anomalous diffusion. It is assumed that the deterministic process corresponds to unknown biological rules which determine the DNA path, whereas the noise mimics the influence of an infinite-dimensional environment on the biological process under study. We prove that the resulting diffusion process, if the effect of the random process is neglected, is an a-stable Levy process with 1 < a < 2. We also show that, if the diffusion process is determined by the joint action of the deterministic and the random process, the correlation effects of the "deterministic dynamics" are cancelled on the short-range scale, but show up in the long-range one. We denote our prescription to generate statistical sequences as the Copying Mistake Map (CMM). We carry out our analysis of several DNA sequences, and of their CMM realizations, with a variety of techniques, and we especially focus on a method of regression to equilibrium, which we call the Onsager Analysis. With these techniques we establish the statistical equivalence of the real DNA sequences with their CMM realizations. We show that long-range correlations are present in exons as well as in introns, but are difficult to detect, since the exon "dynamics" is shown to be determined by theentaglement of three distinct and independent CMM's. Finally we study the validity of the stationary assumption in DNA sequences and we discuss a biological model for the short-range random process based on a folding mechanism of the nucleic acid in the cell nucleus.

In this project, a fast accurate global pairwise alignment of noncoding DNA sequences, MCALIGN2, is developed based on explicit models of indel evolution. A pair-hidden-Markov-Model (pair-HMM) of seven states and a golden-Section-Search algorithm are employed in this method to search for the most probable alignment between two homologous sequences. This method is then used to align and analyze noncoding DNA sequences in Drosophila. Comparative genomic analysis in this project shows that INE-1 elements, one of the most abundant TEs in Drosophila, along with sites within short introns and fourfold degenerate sites are the fastest evolving nucleotides in the genomes of Drosophila melanogaster, D. simulans and D. sechellia. Fourfold sites tend to be evolving (relatively) slightly more slowly than the other two classes of nucleotides, probably due to selection acting on protein translation efficiency. The observed substitution rate in these fastest evolving sites appears to be strongly influenced by the recombinational environment in which they are located. This rate may be influenced by several factors including ancestral polymorphisms, variation in mutation rate, natural selection and random genetic drift. The relative importance of these factors varies depending on the time since speciation. This project also fully investigates the distribution and rate of evolution of three major TE classes (LTR, non-LTR retrotransposons and DNA transposons) in the Drosophila euchromatic genomeusing a gene-centric approach. The study demonstrates that LTR elements outnumber non-LTR and DNA elements in all intergenic, intronic and exonic regions, and LTR elements also show relatively lower mean divergences than the other two classes between D. melanogaster and D. yakuba. The findings suggest that some TEs, rather than being “junk” and “selfish”, may be conserved between species, and therefore, play vital roles in gene regulation and host genome evolution.

A Charomid ordered array library containing the 2-16kb size fraction of MboI-digested canine genomic DNA was screened with the multilocus probes, 33.6 and 33.15. Testing for polymorphism of the minisatellite loci in 48 resulting positive clones yielded seven polymorphic minisatellites with heterozygosities in the range 20-88%. Mendelian inheritance was confirmed shown for two of the polymorphic minisatellites. DNA fingerprinting studies of the level of inter- and intra-breed variation did not show any significant difference between the two. Analysis of intra-breed variation in Bedlington Terriers using two polymorphic minisatellites as single-locus probes revealed a significant reduction in the number of alleles in comparison with an agglomerated population sample, consistent with the high level of inbreeding within this breed. Multi-locus canine minisatellite probe analysis of unrelated species showed that related repeat sequences are present in numerous species. Use of single-locus canine minisatellite probes to analyse related canids suggested that polymorphic canine minisatellites are likely to show transience in their variability and detection, whereas monomorphic minisatellites are stable and more readily detected in related canids. Use of cCfaMP5, the most polymorphic canine minisatellite isolated to date, as a single-locus probe in paternity analysis demonstrates its applicability to forensic problems. Flanking sequence and partial repeat sequence data obtained for the minisatellite in cCfaMP5. The variable region in this minisatellite region is similar to many human minisatellites which show a distinct purine or pyrimidine strand bias. A mechanism whereby this minisatellite might have evolved is suggestedon the basis of the distribution and kinds of repeat units. An initial MVR-PCR analysis of CfaMP5 has been carried out and, with future optimization, it should be possible to digitally type canine minisatellite alleles, thereby widening the scope of the analysis of canine minisatellite variation.

TITLE: DNA INTERFACES FOR ELECTROCHEMICAL DETECTION OF NEURODEGENERATIVE REPEAT SEQUENCES DNA repeat sequences in the human genome possess unique biophysical properties due to their sequence-directed structural flexibility. It has been assumed that unique helical flexibility of these sequences forms non-canonical structures inside the cell that disrupts transcription/translation functions and can lead to variety of fatal diseases such as neurodegenerative disorders. Neorodegenerative diseases are caused by certain types of mutations called repeat expansions. Expansion of certain trinucleotide repeat (TNR) sequences have been associated with almost two dozen neurodegenerative and neuromuscular diseases, such as CGG expansion with Fragile X, CAG repeats with Huntington’s disease (HD), CTG repeats with Myotonic Dystrophy, and GAA expansion with Friedreich’s Ataxia depending on their gene location and threshold length. Current diagnosis of repeat expansion disorders includes traditional techniques including two-dimensional gel electrophoresis and various polymerase chain reaction (PCR) based methods. However, these methods are complicated, high cost, frequently generate false negatives, and are time-consuming procedures. Therefore, to develop rapid and sensitive detection tools, a number of researchers have employed electrochemical strategies for detection of TNR sequences and their lengths using electroactive labels and enzyme-linked steps for signal amplification. However, an urgent need exists for further exploration in this area in order to develop label-free, low-cost, and simple biosensing platforms to detect such unique sequences. In this dissertation we investigated the properties of repeat sequences associated with neurodegenerative diseases to characterize and develop low-cost, label-free, and printable electrochemical platforms to detect TNR sequences. First, surface probe microscopy and electrochemical methods were employed for characterization of TNR sequences and showed that the properties of TNRs are sequence dependent rather than by flexibility rank as had been previously reported for them. Then, the interface properties of these repeat sequences were studied on the surface of two-dimensional materials such as graphene and molybdenum disulfide. Finally, we reported a label-free, low-cost, and simple inkjet printable platform to distinguish the CGG expansion associated with Fragile-X disease.

Mestrado em Engenharia Eletrónica e Telecomunicações
A capacidade de efectuar pesquisas de sequências de ADN similares a outras contidas numa sequência maior, tal como um cromossoma, tem um papel muito importante no estudo de organismos e na possível ligação entre espécies diferentes. Apesar da existência de várias técnicas e algoritmos, criados com o intuito de realizar pesquisas de sequência, este problema ainda está aberto ao desenvolvimento de novas ferramentas que possibilitem melhorias em relação a ferramentas já existentes. Esta tese apresenta uma solução para pesquisa de sequências, baseada em compressão de dados, ou, mais especificamente, em modelos de contexto finito, obtendo uma medida de similaridade entre uma referência e um alvo. O método usa uma abordagem com base em modelos de contexto finito para obtenção de um modelo estatístico da sequência de referência e obtenção do número estimado de bits necessários para codificação da sequência alvo, utilizando o modelo da referência. Ao longo deste trabalho, estudámos o método descrito acima, utilizando, inicialmente, condições controladas, e, por m, fazendo um estudo de regiões de ADN do genoma humano moderno, que não se encontram em ADN ancestral (ou se encontram com elevado grau de dissimilaridade).
The ability to search similar DNA sequences with relation to a larger sequence, such as a chromosome, has a really important role in the study of organisms and the possible connection between di erent species. Even though several techniques and algorithms, created with the goal of performing sequence searches, already exist, this problem is still open to the development of new tools that exhibit improvements over currently existent tools. This thesis proposes a solution for sequence search, based on data compression, or, speci cally, nite-context models, by obtaining a measure of similarity between a reference and a target. The method uses an approach based on nite-context models for the creation of a statistical model of the reference sequence and obtaining the estimated number of bits necessary for the codi cation of the target sequence, using the reference model. In this work we studied the above described method, using, initially, controlled conditions, and, nally, conducting a study on DNA regions, belonging to the modern human genome, that can not be found in ancient DNA (or can only be found with high dissimilarity rate).

The recent explosion of DNA sequence information has provided compelling evidence for the following facts. (1) Simple repetitive sequences-microsatellites and minisatellites occur commonly in the human genome and (2) these repetitive DNA sequences could play an important role in the regulation of various genetic processes including modulation of gene expression. These sequences exhibit extensive polymorphism in both length and the composition between species and between organisms of the same species and even cells of the same organism. The repetitive DNA sequences also exhibit structural polymorphism depending on the sequence composition. The functional significance of repetitive DNA is a well-established fact. The work done in many laboratories including ours has conclusively documented the functional role played by repetitive sequences in various cellular processes. Structural studies have established the sequence requirement for various non-B DNA structures and the functional significance of these unusual DNA structures is becoming increasingly clear. The structures that were characterised earlier purely from conformation point of view have aroused interest after the recent realisation that these structures could be formed in vivo when cloned in a supercoiled plasmid. The discovery of novel type of dynamic mutations where intragenic amplifications of trinucleotide repeats is associated with phenotypic changes causing many neurodegenerative disorders has provided the most compelling evidence for the importance of simple repeats in the etiology of these disorders. Secondary structures adopted by these simple repeats is a common causative factor in the mechanism of expansion of these repeats. This realisation prompted many investigations into the relationship between the DNA sequence, structure and molecular basis of dynamic mutation. Many experimental evidences have implicated paranemic DNA structures in various biological processes, especially in the regulation of gene expression. Earlier work done in our laboratory on the structure function relationship of repetitive DNA sequences provided experimental evidence for the role of paranemic DNA structure in the regulation of gene expression. It was demonstrated that intramolecular triplex potential sequences within a gene downregulate its expression in vivo (Sarkar and Brahmachari (1992) Nucleic Acids Res., 20, 5713-5718). Similarly the effect of cruciform structure forming sequences on gene expression was also documented. Sequence specific alterations in DNA structures were studied in our laboratory using a variety of biophysical and biochemical techniques. An intramolecular, antiparallel tetraplex structure was proposed for human telomeric repeat sequences (Balagurumoorthy, et al., (1994) J. Biol. Chem., 269, 21858-21869). The telomeric repeats are not only present at the end of chromosomes but they are also present at many interstitial sites in the human genome. Database search reveals that the human telomeric sequences as well as similar sequences with minor variations are present at many locations in the human genome. Telomeric repeats are GC rich sequences with the G rich strand protruding as a 3' end overhang at the end of chromosomes. When human telomeric repeats are cloned in a supercoiled plasmid, the C rich strand adopts a hairpin like conformation where as the G-rich strand extrudes into a quadruplex structure. However, the biological significance of these structures in vivo still remains to be elucidated completely. The role of a putative tetraplex DNA structure in the insulin gene linked polymorphic region of the human insulin gene in vivo in the regulation of expression of the insulin gene has been suggested. In this context, we have addressed the question whether the telomeric repeats when present within a gene affect its expression in vivol If so, what would be the possible mechanism? An attempt has been made to understand the effect of presence of telomeric repeats within a gene on its expression. The details of these studies have been presented in Chapter 2 of this thesis. Contrary to telomeric repeats which provide stability to the chromosomes, recently expansion of a GC rich dodecamer repeat upstream of cystatin B gene (chromosome 21q) has been shown to be the most common mutation associated with Progressive Myoclonus Epilepsy (EPM1) of Unverricht-Lundberg type. Two to three copies of the repeat (CCCCGCCCCGCG)n are present in normal individuals whereas the affected individuals have 30-75 copies of this repeat. The expression of cystatin B gene is reduced in patients in a cell specific manner. The repeat also shows intergenerational variability. The exact mechanism of expansion of this repeat is not known. In the case of trinucleotide repeat expansion, it is shown that the structure adopted by the repeat plays an important role in the mechanism of expansion and that some of the secondary structures adopted by trinucleotide repeats could be inherently mutagenic conformations. In order to understand the mechanism of expansion EPM1 dodecamer repeat, the work reported in this thesis was carried out with the following objectives. • To understand the structure of G rich and C-rich strands of EPM1 repeat. • To understand the variations in the structure with the increase in the length and its possible implications in the mechanism of expansion of EPM 1 repeat. Studies aimed with these objectives are presented in chapters 3, 4 and 5 of the thesis. Chapter 1 provides a general introduction to repetitive DNA, the various structures adopted by repetitive DNA sequences in the genome, the functional significance of the various simple repetitive DNA sequences in the genome has been presented. An account of trinucleotide repeat expansion and associated disorders, non-trinucleotide repeat expansions and associated disorders has been presented. The various non B-DNA structures adopted these repeats and their implications in the mechanism of expansion have been discussed. Chapter 2 describes in frame cloning of human telomeric repeats d(G3T2A)3G3 in the N-terminal region of β-galactosidase gene. The effect of such repeat Sequences on transcription elongation in vivo has been studied using E.coli as a model system. The 3.5 copies of human telomeric repeat sequences were cloned in the sense strand of plasmid pBluescriptllSK+ so as to create plasmid clone pSBQ8 and in the template strand of plasmid pBluescriptHKS+ so as to create clone pSBRQ8. One dimensional chloroquine gel shift assay indicated presence of an unwound structure in pSBQ8 and pSBRQ8. β-galactosidase activity assay suggested downregulation of the gene in vivo. In the case of plasmid pSBQ8 the difference in β-galactosidase activity was approximately 6 fold as compared to the parent plasmid pBluescriptIISK+ whereas in the case of pSBRQ8 the difference in β-galactosidase activity was approximately 8 fold as compared to the control pBluescriptIIKS+. The analysis of β-galactosidase transcript showed that full length transcript was formed in the case of pSBQ8. Full length transcript was not formed in the case of pSBRQ8. We propose that in the case of pSBQ8 the gene expression is inhibited in steps subsequent to transcription elongation. In the case of pSBRQ8, we propose that quadruplex structure may be formed by the template strand at the DNA level thereby blocking transcription elongation step. Chapter 3 describes studies aimed at understanding the structure of G-rich strand (referred to as G strand) of Progressive Myoclonus Epilepsy (EPM1) repeat. The sequence of the G strand of dodecamer EPM1 repeat is d(GGGGCGGGGCGC)n. Oligoucleotides containing one (12mer), two (24mer) and three(36mer) were synthesised. These oligonucleotides are referred to as dG12, dG24 and dG36 respectively. Structural studies were carried out using CD spectroscopy, UV melting, non-denaturing gel electrophoresis and chemical and enzymatic probing. The G strand oligonucleotides showed enhanced gel elecrophoretic mobility in the presence of monovalent cations KCl and NaCl. Oligonucleotide dG12 also showed retarded species on non-denaturing gel in the presence of 70mM KCl indicating intermolecular associations. Oligonucleotides dG24 and dG36 predominantly formed intramolecular structures which migrated anomalously faster than the expected size. The CD spectrum for dG12 showed an intense positive band at 260nm and a negative band at 240nm in the presence of KCl indicative of an intermolecular, parallel G quartet structure. The CD spectra of dG24 and dG36 showed 260nm positive peak, 240nm negative peak along with a positive band around 290nm. This is indicative of folded back structure. These findings support the results of non-denaturing gel electrophoresis of G strand oligonucleotides. The UV melting profiles suggested increase in the stability with the increase in the length. These structures were further characterised by PI nuclease and chemical probing using DMS and DEPC. The structural studies with G-rich strand of EPM1 dodecamer repeat showed that this repeat motif adopts intramolecularly folded structures with increase in the length of the repeat thereby favouring slippage during replication. Chapter 4 deals with the studies aimed at understanding the structure at acidic pH of C-rich strand (referred to as C strand) of Progressive Myoclonus Epilepsy (EPM1) repeat. The sequence of the C strand of dodecamer EPM1 repeat is d(CCCCGCCCCGCG)n. The C rich oligonucleotides are known to form a four stranded structure called i-motif at acidic pH involving intercalated base pairs. The i-motif consists of two parallel stranded, base paired duplexes are arranged in an antiparallel orientation. Since, the base pairs of one base paired duplex intercalate into those of the other duplex, the structure is called as i-motif. We have investigated structure of C strand of EPM1 repeat by circular dichroism (CD), native polyacrylamide gel electrophoresis and UV melting. Oligonucleotide dC12 showed two bands of which the major band was retarded on the native gel (pH 5.0) at low temperature suggesting that dC12 predominantly formed intermolecular structure, Oligonucleotides dC24 and dC36 migrated anomalously faster than the expected size indicating formation of compact, intramolecularly folded structures. Circular dichroism studies indicate that, all the oligonucleotides displayed an intense positive band near 285nm, a negative band around 260nm with a cross over at 270nm, This is a characteristic CD signature for an i-motif structure and reflects the presence of secondary structure due to formation of hydrogen bonded pairs between protonated cytosines. All the C strand oligonucleotides showed hyperchromism at 265nm, which is an isobestic wavelength for C protonation. Studies described in this chapter suggest an intramolecular i-motif structure for dC24 and dC36 and an intermolecular i-motif for oligonucleotide dC12. In addition, it was interesting to note that inspite of the presence of G residues, the stretch of C residues could adopt i-motif structure. Although these structures are formed at an acidic pH, it is indicative of formation of possible intramolecularly folded structure. Many reports have suggested the possibility of cytosine rich sequences adopting i-motif structure even at neutral pH. In order to test this possibility, structural studies were carried out on the C strand EPM1 oligonucleotides at pH 7.2 in the presence of 70mM NaCl. These studies have been described in Chapter 5. The investigations were done using CD spectroscopy, UV melting, native polyacrylamide gel electrophoresis, and chemical probing using hydroxylamine and PI nuclease. These studies indicate that all the C strand oligonucleotides form intramolecular, hairpin structure at physiological pH. All the three C strand oligonucleotides migrated anomalously faster on the native gel indicating the presence of a compact structure. The CD spectra at pH 7.2 showed a blue shift as compared to those at pH 5.0. This indicated absence of base pairs. The hydroxylamine chemical probing suggested presence of G-C Watson-Crick base pairs. The loop residues of the folded back hairpin structures were probed with PI nuclease. The C strand oligonucleotides showed possibility of formation of multiple hairpin structures with the increase in the length of the repeat. The propensity to form hairpin structures suggests a possibility of formation of slip loop structures during the replication process thereby promoting expansion of this repeat. Formation of folded back hairpin like structures is significant in terms of mechanism of expansion of this repeat. Chapter 6 is devoted to concluding remarks highlighting the significance of the experimental results presented in this thesis and their possible biological implications in the light of contemporary research.

In an investigation which concentrated primarily on the two completely sequenced chloroplast genomes, one from a tobacco and one from a liverwort, an attempt has been -made to discover some of the factors which produce order in DNA sequences. This was done by 1. looking in detail at doublet organization throughout the genomes, 2'. by examining the ability of different methods to predict the existence of genes, based only on sequence organization and 3. by employing information theorj' to explore various levels of ordering in these sequences. The doublet analysis was performed on seven categories of DNA: tDNA, rDNA, ribosomal proteins, open reading frames not known to be genes (URF), other protein genes, non coding regions and introns. The rDNA has the most unusual doublet properties of all categories although all categories have, to a considerable extent, similar doublet properties. I suggest that these particular doublet properties facilitate accurate replication of the genome. In addition it appears that doublets which have certain thermodynamic properties are more abundant that others, suggesting that there is a selection pressure at the level of doublets for certain thermodynamic properties. Nussinov's hypothesis, that complementary doublets have similar relative abundances due to inverted duplication events has been tested and would not seem to explain the phenomenon. Fickett's method to predict whether URFs are genes was more successful than Sheperd's method. Fickett's method was modified for use on the chloroplast genomes and its rate of successful prediction increased substantially. This modified method will be useful for other chloroplast genomes as they are sequenced and also supports Fickett's contention that the method could be improved for use on specific groups. The ability to predict genes based only on sequence data shows that the requirement to code for protein exerts a detectable amount of order on the gene sequence and that this order is distinguishable from the order in non coding regions. Nearly all URFs greater than 200 base pairs in both plants are predicted to be genes. Informational analysis showed that most order is at the level of single and double bases with a significant, lesser amount of order at the triplet and 4-plet level. This was true for both coding and noncoding regions in both plants. This is in contrast earlier work (Rowe and Trainor) which found that in viruses there was a significant difference between 4-plet ordering in coding and noncoding regions. It is suggested that DNA may be optimized for replication rather than protein production. Several new problems and experiments have been suggested.
Science, Faculty of
Botany, Department of
Graduate

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
Includes bibliographical references (p. 63-65).
The advent of DNA sequencing has revolutionized biological research by providing virtual blueprints of living organisms and offering insights into complicated biochemical processes. DNA sequencing is a process encompassing both chemical reactions and signal processing techniques to identify the order of chemical bases in a DNA molecule. In this thesis, we focus on the base-calling stage, during which base order is estimated from data collected through electrophoresis and florescence detection. In particular, we examine the possibility of jointly base-calling two superposed DNA sequences by applying the sum-product algorithm on factor graphs. This approach allows a single electrophoresis experiment to process two sequences, using the same quantity of reagents and machine hours as for a single sequence. A practical heuristic is first used to estimate the peak parameters, then separate those into two sequences (major/minor) by passing messages on a factor graph. Base-calling on the major alone yields accuracy commensurate with single sequence approaches, and joint base-calling provides results for the minor which, while being of lesser quality, incurs no additional cost and can be ultimately used in the genome assembly process.
by Xiaomeng Shi.
S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Chemical Engineering, 2004.
Includes bibliographical references.
(cont.) algorithm was validated on synthetic as well as real datasets. When tested on a set of 30 well-studied regulons in Escherichia Coli, with known instances of regulatory motifs collected from biological literature, the algorithm showed, in 14 cases, a high sensitivity and specificity of 70% and 80%, respectively. TABS was shown to perform better than two other popular state-of-the-art motif-finding algorithms. In addition, its applicability on synthetic microarray-like data was demonstrated. Several significant novel motifs detected by the algorithm that form good targets for investigation of regulatory function by biological experiments were reported.
One of the major challenges facing biologists is to understand the mechanisms governing the regulation of gene expression. Completely sequenced genomes, together with the emerging DNA microarray technologies have enabled the measurement of gene expression levels in cell cultures and opened new possibilities for studying gene regulation. A fundamental sub-problem in unraveling regulatory interactions in both prokaryotes and eukaryotes is to identify common binding sites or promoters in the regulatory regions of genes. For a gene's mRNA to be expressed, a class of proteins called transcription factors must bind to the cis-regulatory elements on the DNA sequence upstream of the gene, to enhance RNA polymerase binding and hence initiate transcription. These binding sites are believed to be located within several hundred base pairs upstream of the respective ORFs. Biological methods for discovering regulatory binding sites are slow and time consuming. To address this problem, several heuristic-based computational methods have been developed in the past with either of two approaches--sequence-driven or pattern-driven. In this dissertation, we propose a novel approach for finding shared motifs in DNA sequences based on an exhaustive pattern enumeration algorithm, that combines the benefits of the pattern-driven and sequence-driven approaches. We developed TABS, a method that identifies local regions of high similarity by clustering statistically significant patterns to obtain putative binding sites. The method assumes minimal apriori information about the sites and can detect signals in a subset of the input sequences, making it amenable for motif-discovery in gene clusters obtained from microarray experiments. The performance of the
by Vipin Gupta.
Ph.D.

Hung Wah Johnson.
Thesis submitted in: August 2004.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2005.
Includes bibliographical references (leaves 116-121).
Abstracts in English and Chinese.
Abstract --- p.i
Acknowledgement --- p.iv
Chapter 1 --- Introduction --- p.1
Chapter 1.1 --- Motivation --- p.1
Chapter 1.2 --- Problem Statement --- p.3
Chapter 1.3 --- Outline of the thesis --- p.6
Chapter 2 --- Background --- p.8
Chapter 2.1 --- Biological Background --- p.8
Chapter 2.2 --- Sequence Alignments --- p.9
Chapter 2.2.1 --- Pairwise Sequences Alignment --- p.11
Chapter 2.2.2 --- Multiple Sequences Alignment --- p.15
Chapter 2.3 --- Neighbor Joining Tree --- p.16
Chapter 2.4 --- Marker Extractions --- p.18
Chapter 2.5 --- Neural Network --- p.19
Chapter 2.6 --- Conclusion --- p.22
Chapter 3 --- Related Work --- p.23
Chapter 3.1 --- FASTA --- p.23
Chapter 3.2 --- Suffix Tree --- p.25
Chapter 4 --- Sub-Sequence Segmentation Tree --- p.28
Chapter 4.1 --- Introduction --- p.28
Chapter 4.2 --- Problem Statement --- p.29
Chapter 4.3 --- Design --- p.33
Chapter 4.4 --- Time and space complexity analysis --- p.38
Chapter 4.4.1 --- Performance Evaluation --- p.40
Chapter 4.5 --- Summary --- p.48
Chapter 5 --- Applications: Global Sequences Alignment --- p.51
Chapter 5.1 --- Introduction --- p.51
Chapter 5.2 --- Problem Statement --- p.53
Chapter 5.3 --- Pairwise Alignment --- p.53
Chapter 5.3.1 --- Algorithm --- p.53
Chapter 5.3.2 --- Time and Space Complexity Analysis --- p.64
Chapter 5.4 --- Multiple Sequences Alignment --- p.67
Chapter 5.4.1 --- The Clustalw Algorithm --- p.68
Chapter 5.4.2 --- MSA Using SSST --- p.70
Chapter 5.4.3 --- Time and Space Complexity Analysis --- p.70
Chapter 5.5 --- Experiments --- p.71
Chapter 5.5.1 --- Experiment Setting --- p.72
Chapter 5.5.2 --- Experimental Results --- p.72
Chapter 5.6 --- Summary --- p.80
Chapter 6 --- Applications: Marker Extractions --- p.81
Chapter 6.1 --- Introduction --- p.81
Chapter 6.2 --- Problem Statement --- p.82
Chapter 6.3 --- The Multiple Sequence Alignment Approach --- p.85
Chapter 6.3.1 --- Design --- p.85
Chapter 6.4 --- Reference Sequence Alignment Approach --- p.88
Chapter 6.4.1 --- Design --- p.90
Chapter 6.5 --- Time and Space Complexity Analysis --- p.95
Chapter 6.6 --- Experiments --- p.95
Chapter 6.7 --- Summary --- p.99
Chapter 7 --- HBV Application Framework --- p.101
Chapter 7.1 --- Motivations --- p.101
Chapter 7.2 --- The Procedure Flow of the Application --- p.102
Chapter 7.2.1 --- Markers Extractions --- p.103
Chapter 7.2.2 --- Rules Training and Prediction --- p.103
Chapter 7.3 --- Results --- p.105
Chapter 7.3.1 --- Clustering --- p.106
Chapter 7.3.2 --- Classification --- p.107
Chapter 7.4 --- Summary --- p.110
Chapter 8 --- Conclusions --- p.112
Chapter 8.1 --- Contributions --- p.112
Chapter 8.2 --- Future Works --- p.114
Chapter 8.2.1 --- HMM Learning --- p.114
Chapter 8.2.2 --- Splice Sites Learning --- p.114
Chapter 8.2.3 --- Faster Algorithm for Multiple Sequences Alignment --- p.115
Bibliography --- p.121

A pattern is a relatively short sequence that represents a phenomenon in a set of sequences. Not all short sequences are patterns; only those that are statistically significant are referred to as patterns or motifs. Pattern discovery methods analyze sequences and attempt to identify and characterize meaningful patterns. This thesis extends the application of pattern discovery algorithms to a new problem domain - Single Nucleotide Polymorphism (SNP) classification. SNPs are single base-pair (bp) variations in the genome, and are probably the most common form of genetic variation. On average, one in every thousand bps may be an SNP. The function of most SNPs, especially those not associated with protein sequence changes, remains unclear. However, genome-wide linkage analyses have associated many SNPs with disorders ranging from Crohn’s disease, to cancer, to quantitative traits such as height or hair color. As a result, many groups are working to predict the functional effects of individual SNPs. In contrast, very little research has examined the causes of SNPs: Why do SNPs occur where they do? This thesis addresses this problem by using pattern discovery algorithms to study DNA non-coding sequences. The hypothesis is that short DNA patterns can be used to predict SNPs. For example, such patterns found in the SNP sequence might block the DNA repair mechanism for the SNP, thus causing SNP occurrence. In order to test the hypothesis, a model is developed to predict SNPs by using pattern discovery methods. The results show that SNP prediction with pattern discovery methods is weak (50 2%), whereas machine learning classification algorithms can achieve prediction accuracy as high as 68%. To determine whether the poor performance of pattern discovery is due to data characteristics (such as sequence length or pattern length) or to the specific biological problem (SNP prediction), a survey was conducted by profiling eight representative pattern discovery methods at multiple parameter settings on 6,754 real biological datasets. This is the first systematic review of pattern discovery methods with assessments of prediction accuracy, CPU usage and memory consumption. It was found that current pattern discovery methods do not consider positional information and do not handle short sequences well (<150 bps), including SNP sequences. Therefore, this thesis proposes a new supervised pattern discovery classification algorithm, referred to as Weighted-Position Pattern Discovery and Classification (WPPDC). The WPPDC is able to exploit positional information to identify positionally-enriched motifs, and to select motifs with a high information content for further classification. Tree structure is applied to WPPDC (referred to as T-WPPDC) in order to reduce algorithmic complexity. Compared to pattern discovery methods T-WPPDC not only showed consistently superior prediction accuracy and but generated patterns with positional information. Machine-learning classification methods (such as Random Forests) showed comparable prediction accuracy. However, unlike T-WPPDC, they are classification methods and are unable to generate SNP-associated patterns.

碩士
國立中山大學
資訊工程學系研究所
91
Recently, the prediction of promoters has attracted many researchers'' attention. Unfortunately, most previous prediction algorithms did not provide high enough sensitivity and specificity. The goal of this thesis is to develop an efficient prediction algorithm that can increase the detection power (power = 1 - false negative). We do not try to find more distinct features in promoters one by one, such as transcriptional elements. Our main idea is to use the computer power to calculate all possible patterns which are the possible features of promoters. Accordingly, we shall define some scoring methods for training a given set of sequences, which involve promoter sequences and non-promoter sequences. Then, we can obtain a threshold value for determining whether a testing sequence is a promoter or not. By the experimental results, our prediction has higher correct rate than other previous methods.