New Contig Creation Algorithm for the de novo DNA Assembly Problem

DNA assembly is among the most fundamental and difficult problems in bioinformatics. Near optimal assembly solutions are available for bacterial and small genomes, however assembling large and complex genomes especially the human genome using Next-Generation-Sequencing (NGS) technologies is shown to be very difficult because of the highly repetitive and complex nature of the human genome, short read lengths, uneven data coverage and tools that are not specifically built for human genomes. Moreover, many algorithms are not even scalable to human genome datasets containing hundreds of millions of short reads. The DNA assembly problem is usually divided into several subproblems including DNA data error detection and correction, contig creation, scaffolding and contigs orientation; each can be seen as a distinct research area. This thesis specifically focuses on creating contigs from the short reads and combining them with outputs from other tools in order to obtain better results. Three different assemblers including SOAPdenovo [Li09], Velvet [ZB08] and Meraculous [CHS+11] are selected for comparative purposes in this thesis. Obtained results show that this thesis’ work produces comparable results to other assemblers and combining our contigs to outputs from other tools, produces the best results outperforming all other investigated assemblers.

Foraging ecology and parental behaviour in the common tern (Sterna hirundo)

One component of successful parenting is related to efficiency in foraging behaviour. The relationships among chick feeding, the size and type of food package, and length of parental foraging trips has not been well studied in seabirds. In addition, relatively few data have been collected on the activities of seabirds when foraging away from the nest site. The objectives of this study were: (1) to contrast productivity, feeding rate, and attendance patterns of individuals carrying a novel transmitter with a control group of birds; (2) to use radio-telemetry to assess the variability in foraging locations within and between individual male Common Terns; (3) to determine the seasonal variation in chick diet; (4) to determine for each transmittered bird, the relationships among the foraging patterns, parental behaviour, and seasonal reproductive success. The study took place over two years (1990-91) on a concrete breakwater 1 km offshore on Lake Erie near Port Colbome, Ontario. Ten pairs of terns in 1990 and 12 pairs in 1991 were radio-tracked by boat or car during the chick rearing stage. Concurrent behavioural observations documented the time each sex spent foraging or at the nest. The frequency and prey species composition of feeds to chicks were also recorded. The transmitters had negligible effects on the feeding frequency and brood attendance patterns of transmitter carrying birds. Peak nesting transmittered birds in 1990 and 1991 exhibited some inter-individual variability in foraging locations, however intraindividual variability was low. Birds foraged primarily to the west and northwest of the colony. Late nesters exhibited greater inter-individual variability, however intra-individual variability remained low for most birds. Neither group demonstrated sufficient variability to support the regular use of this colony as an "information centre". Individual transmittered birds had unique and predictable foraging patterns, and corresponding differences in feeding frequencies and brood attendance patterns, yet productivity was essentially equal between nests due to the impact and importance of stochastic events. Individuals that were recaptured in 1991 exhibited very similar foraging patterns to 1990, suggesting littie variability between years. Conservation of foraging patterns between years may have potential implications for mate choice decisions in future breeding seasons. Prey species delivered to chicks differed between morning and evening for peak and late nesters in 1990, but not 1991. Peak nesters in 1990 fed significantiy more Rainbow Smelt fOsmerus mordM) than Emerald Shiner (Notropis atherinoidesV this trend was reversed for late nesters who also fed large numbers of unidentified larval fish. No significant differences were found in 1991. Seasonal changes in prey species delivered to chicks is believed to be attributable to the temperature tolerances of the smelt and shiners, and the presence of large schools of larval fish during the late nesting season.

Analytical modelling of bacterial migration and accumulation with rate-limited sorption in discrete fractures

An analytical model for bacterial accumulation in a discrete fractllre has been developed. The transport and accumlllation processes incorporate into the model include advection, dispersion, rate-limited adsorption, rate-limited desorption, irreversible adsorption, attachment, detachment, growth and first order decay botl1 in sorbed and aqueous phases. An analytical solution in Laplace space is derived and nlln1erically inverted. The model is implemented in the code BIOFRAC vvhich is written in Fortran 99. The model is derived for two phases, Phase I, where adsorption-desorption are dominant, and Phase II, where attachment-detachment are dominant. Phase I ends yvhen enollgh bacteria to fully cover the substratllm have accllillulated. The model for Phase I vvas verified by comparing to the Ogata-Banks solution and the model for Phase II was verified by comparing to a nonHomogenous version of the Ogata-Banks solution. After verification, a sensitiv"ity analysis on the inpllt parameters was performed. The sensitivity analysis was condllcted by varying one inpllt parameter vvhile all others were fixed and observing the impact on the shape of the clirve describing bacterial concentration verSllS time. Increasing fracture apertllre allovvs more transport and thus more accllffilliation, "Vvhich diminishes the dllration of Phase I. The larger the bacteria size, the faster the sllbstratum will be covered. Increasing adsorption rate, was observed to increase the dllration of Phase I. Contrary to the aSSllmption ofllniform biofilm thickness, the accllffilliation starts frOll1 the inlet, and the bacterial concentration in aqlleous phase moving towards the olitiet declines, sloyving the accumulation at the outlet. Increasing the desorption rate, redllces the dliration of Phase I, speeding IIp the accllmlilation. It was also observed that Phase II is of longer duration than Phase I. Increasing the attachment rate lengthens the accliffililation period. High rates of detachment speeds up the transport. The grovvth and decay rates have no significant effect on transport, althollgh increases the concentrations in both aqueous and sorbed phases are observed. Irreversible adsorption can stop accllillulation completely if the vallIes are high.

Foraging ecology and parental care of common terns (Sterna hirundo) nesting in Windermere Basin, Lake Ontario

The relationships among chick feeding, size and type of prey item, and foraging time away from the brood have not been well studied in seabirds. This study investigated spatial and temporal patterns of foraging and chick-provisioning among 23 radio-tagged male common terns nesting at Hamilton Harbour, Lake Ontario during 1991 and 1992. Telemetry data were collected concurrently with behavioural observations from an elevated blind. Terns fitted with transmitters did not differ from controls with respect to either brood attendance, patterns of chick mortality, species and size distributions of prey delivered to offspring, or chick-provisioning rates. There was a clear separation of parental roles: males were primarily responsible for feeding chicks while females allocated more time to brood attendance. The prey species most commonly delivered to chicks by adults were rainbow smelt (Osmerus mordax) and alewife (A/osa pseudoharengus), followed in importance by larval fish, emerald shiner (Notropis antherinoides), salmonids, and fathead minnows (Pimepha/es prome/as). The relative proportions of various fish speCies delivered to chicks by males differed over the course of each breeding season, and there was also much variability in species composition of prey between years. Sizes of prey delivered to chicks also differed between sampling periods. The modal size of fish brought to chicks during Peak 1991 was 1.5 bill lengths, while the majority of prey in Late 1991 were small larval fish. The reverse trend occurred in 1992 when small fish were delivered to chicks predominantly during the Peak nesting period. During periods when predominantly small fish were delivered to chicks, the foraging activity of radio-tagged males was concentrated within a two kilometer radius of the colony. The observed variation in prey composition and foraging locations during the study likely reflects temporal variation in the availability of prey in the vicinity of the colony. Males delivered fish to chicks at a constant rate, while females 4 increased their feeding frequency over the first six to ten brood days. The mean length of fish delivered to chicks by adults increased significantly with increasing chick age. As a group, within each nesting period, transmittered males either foraged predominantly in the same directional bearing (north during Peak 1991, south during Late 1992), or concentrated foraging activity in the immediate vicinity of the colony (Late 1991, Peak 1992). However, individual radio-tagged males exhibited unique and predictable foraging patterns, often favouring specific locations within these areas and differing in their secondary foraging patterns. Overall, the Lake Ontario shoreline between NCB Bay" (3.5 km south of colony) and the lift bridge canal (4 km north of colony) was the foraging area used most frequently by radiotagged males during the chick-rearing period. Foraging patterns of transmittered males at Windermere Basin are similar to patterns of peak-nesting common terns, but differ from those of late-nesters, at a nearby colony (Port Colborne, Lake Erie). Differences between the foraging patterns of late-nesting terns at these colonies likely reflect differences in annual patterns of fish availability between the two locations. No relationship was found between foraging proficiency of adults and survival of offspring. Stochastic factors, such as predation by black-crowned nightherons (Nycticorax nycticorax) and adverse weather conditions during the early stages of chick rearing, may be more important determinants of common tern breeding success than parental quality or fish availability.

X-ray diffraction of a gram-negative bacterial membrane mimetic

This thesis applies x-ray diffraction to measure he membrane structure of lipopolysaccharides and to develop a better model of a LPS bacterial melilbrane that can be used for biophysical research on antibiotics that attack cell membranes. \iVe ha'e Inodified the Physics department x-ray machine for use 3.'3 a thin film diffractometer, and have lesigned a new temperature and relative humidity controlled sample cell.\Ve tested the sample eel: by measuring the one-dimensional electron density profiles of bilayers of pope with 0%, 1%, 1G :VcJ, and 100% by weight lipo-polysaccharide from Pse'udo'lTwna aeTuginosa. Background VVe now know that traditional p,ntibiotics ,I,re losing their effectiveness against ever-evolving bacteria. This is because traditional antibiotic: work against specific targets within the bacterial cell, and with genetic mutations over time, themtibiotic no longer works. One possible solution are antimicrobial peptides. These are short proteins that are part of the immune systems of many animals, and some of them attack bacteria directly at the membrane of the cell, causing the bacterium to rupture and die. Since the membranes of most bacteria share common structural features, and these featuret, are unlikely to evolve very much, these peptides should effectively kill many types of bacteria wi Lhout much evolved resistance. But why do these peptides kill bacterial cel: '3 , but not the cells of the host animal? For gramnegative bacteria, the most likely reason is that t Ileir outer membrane is made of lipopolysaccharides (LPS), which is very different from an animal :;ell membrane. Up to now, what we knovv about how these peptides work was likely done with r !10spholipid models of animal cell membranes, and not with the more complex lipopolysa,echaricies, If we want to make better pepticies, ones that we can use to fight all types of infection, we need a more accurate molecular picture of how they \vork. This will hopefully be one step forward to the ( esign of better treatments for bacterial infections.

The Salmon Algorithm - A New Population Based Search Metaheuristic

This thesis introduces the Salmon Algorithm, a search meta-heuristic which can be used for a variety of combinatorial optimization problems. This algorithm is loosely based on the path finding behaviour of salmon swimming upstream to spawn. There are a number of tunable parameters in the algorithm, so experiments were conducted to find the optimum parameter settings for different search spaces. The algorithm was tested on one instance of the Traveling Salesman Problem and found to have superior performance to an Ant Colony Algorithm and a Genetic Algorithm. It was then tested on three coding theory problems - optimal edit codes, optimal Hamming distance codes, and optimal covering codes. The algorithm produced improvements on the best known values for five of six of the test cases using edit codes. It matched the best known results on four out of seven of the Hamming codes as well as three out of three of the covering codes. The results suggest the Salmon Algorithm is competitive with established guided random search techniques, and may be superior in some search spaces.

A Multi-Objective Genetic Algorithm with Side Effect Machines for Motif Discovery

Understanding the machinery of gene regulation to control gene expression has been one of the main focuses of bioinformaticians for years. We use a multi-objective genetic algorithm to evolve a specialized version of side effect machines for degenerate motif discovery. We compare some suggested objectives for the motifs they find, test different multi-objective scoring schemes and probabilistic models for the background sequence models and report our results on a synthetic dataset and some biological benchmarking suites. We conclude with a comparison of our algorithm with some widely used motif discovery algorithms in the literature and suggest future directions for research in this area.

A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic Representations

Ordered gene problems are a very common classification of optimization problems. Because of their popularity countless algorithms have been developed in an attempt to find high quality solutions to the problems. It is also common to see many different types of problems reduced to ordered gene style problems as there are many popular heuristics and metaheuristics for them due to their popularity. Multiple ordered gene problems are studied, namely, the travelling salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of heuristics and metaheuristics with two distinct types or representations. The majority of the algorithms are built around the Recentering- Restarting Genetic Algorithm. The algorithm variations were successful on all problems studied, and particularly for the two bioinformatics problems. For DNA Error Correction multiple cases were found with 100% of the codes being corrected. The algorithm variations were also able to beat all other state-of-the-art DNA Fragment Assemblers on 13 out of 16 benchmark problem instances.

Disease-Gene Association Using a Genetic Algorithm

Understanding the relationship between genetic diseases and the genes associated with them is an important problem regarding human health. The vast amount of data created from a large number of high-throughput experiments performed in the last few years has resulted in an unprecedented growth in computational methods to tackle the disease gene association problem. Nowadays, it is clear that a genetic disease is not a consequence of a defect in a single gene. Instead, the disease phenotype is a reflection of various genetic components interacting in a complex network. In fact, genetic diseases, like any other phenotype, occur as a result of various genes working in sync with each other in a single or several biological module(s). Using a genetic algorithm, our method tries to evolve communities containing the set of potential disease genes likely to be involved in a given genetic disease. Having a set of known disease genes, we first obtain a protein-protein interaction (PPI) network containing all the known disease genes. All the other genes inside the procured PPI network are then considered as candidate disease genes as they lie in the vicinity of the known disease genes in the network. Our method attempts to find communities of potential disease genes strongly working with one another and with the set of known disease genes. As a proof of concept, we tested our approach on 16 breast cancer genes and 15 Parkinson's Disease genes. We obtained comparable or better results than CIPHER, ENDEAVOUR and GPEC, three of the most reliable and frequently used disease-gene ranking frameworks.

Using PageRank Algorithm in Analyzing Dictionary Graphs and PageRank in Dynamic Graphs

In this thesis we are going to analyze the dictionary graphs and some other kinds of graphs using the PagerRank algorithm. We calculated the correlation between the degree and PageRank of all nodes for a graph obtained from Merriam-Webster dictionary, a French dictionary and WordNet hypernym and synonym dictionaries. Our conclusion was that PageRank can be a good tool to compare the quality of dictionaries. We studied some artificial social and random graphs. We found that when we omitted some random nodes from each of the graphs, we have not noticed any significant changes in the ranking of the nodes according to their PageRank. We also discovered that some social graphs selected for our study were less resistant to the changes of PageRank.