Community Detection in Multi-Layer Networks

In the scope of the current thesis we review and analyse networks that are formed by nodes with several attributes. We suppose that different layers of communities are embedded in such networks, besides each of the layers is connected with nodes' attributes. For example, examine one of a variety of online social networks: an user participates in a plurality of different groups/communities – schoolfellows, colleagues, clients, etc. We introduce a detection algorithm for the above-mentioned communities. Normally the result of the detection is the community supplemented just by the most dominant attribute, disregarding others. We propose an algorithm that bypasses dominant communities and detects communities which are formed by other nodes' attributes. We also review formation models of the attributed networks and present a Human Communication Network (HCN) model. We introduce a High School Texting Network (HSTN) and examine our methods for that network.

Developmental and individual differences in novelty and error detection in 10-year-old children and young adults /

Event-related potentials were recorded from 10-year-old children and young adults in order to examine the developmental dififerences in two frontal lobe functions: detection of novel stimuli during an auditory novelty oddball task, and error detection during a visual flanker task. All participants showed a parietally-maximal P3 in response to auditory stimuli. In children, novel stimuli generated higher P3 amplitudes at the frontal site compared with target stimuli, whereas target stimuli generated higher P3 amplitudes at the parietal site compared with novel stimuli. Adults, however, had higher P3 amplitude to novel tones compared with target tones at each site. Children also had greater P3 amplitude at more parietal sites than adults during the novelty oddball and flanker tasks. Furthermore, children and adults did not show a significant reduction in P3 amplitude from the first to second novel stimulus presentation. No age differences were found with respect to P3 latency to novel and target stimuli. These findings suggest that the detection of novel and target stimuli is mature in 10-year-olds. Error trials typically elicit a negative ERP deflection (the ERN) with a frontal-central scalp distribution that may reflect response monitoring. There is also evidence of a positive ERP peak (the Pe) with a posterior scalp distribution which may reflect subjective recognition of a response. Both children and adults showed an ERN and Pe maximal at frontal-central sites. Children committed more errors, had smaller ERN across sites, and had a larger Pe at the parietal site than adults. This suggests that response monitoring is still immature in 10-year-olds whereas recognition of and emotional responses to errors may be similar in children and adults.

Heuristics for the Critical Node Detection Problem in Large Complex Networks

Complex networks have recently attracted a significant amount of research attention due to their ability to model real world phenomena. One important problem often encountered is to limit diffusive processes spread over the network, for example mitigating pandemic disease or computer virus spread. A number of problem formulations have been proposed that aim to solve such problems based on desired network characteristics, such as maintaining the largest network component after node removal. The recently formulated critical node detection problem aims to remove a small subset of vertices from the network such that the residual network has minimum pairwise connectivity. Unfortunately, the problem is NP-hard and also the number of constraints is cubic in number of vertices, making very large scale problems impossible to solve with traditional mathematical programming techniques. Even many approximation algorithm strategies such as dynamic programming, evolutionary algorithms, etc. all are unusable for networks that contain thousands to millions of vertices. A computationally efficient and simple approach is required in such circumstances, but none currently exist. In this thesis, such an algorithm is proposed. The methodology is based on a depth-first search traversal of the network, and a specially designed ranking function that considers information local to each vertex. Due to the variety of network structures, a number of characteristics must be taken into consideration and combined into a single rank that measures the utility of removing each vertex. Since removing a vertex in sequential fashion impacts the network structure, an efficient post-processing algorithm is also proposed to quickly re-rank vertices. Experiments on a range of common complex network models with varying number of vertices are considered, in addition to real world networks. The proposed algorithm, DFSH, is shown to be highly competitive and often outperforms existing strategies such as Google PageRank for minimizing pairwise connectivity.

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.

Potential Urinary Protein Biomarker Candidates for the Accurate Detection of Prostate Cancer among Benign Prostatic Hyperplasia Patients

Globally, Prostate cancer (PCa) is the most frequently occurring non-cutaneous cancer, and is the second highest cause of cancer mortality in men. Serum prostate specific antigen (PSA) has been the standard in PCa screening since its approval by the American Food & Drug Administration (FDA) in 1994. Currently, PSA is used as an indicator for PCa - patients with a serum PSA level above 4ng/mL will often undergo prostate biopsy to confirm cancer. Unfortunately fewer than similar to 30% of these men will biopsy positive for cancer, meaning that the majority of men undergo invasive biopsy with little benefit. Despite PSA's notoriously poor specificity (33%), there is still a significant lack of credible alternatives. Therefore an ideal biomarker that can specifically detect PCa at an early stage is urgently required. The aim of this study was to investigate the potential of using deregulation of urinary proteins in order to detect Prostate Cancer (PCa) among Benign Prostatic Hyperplasia (BPH). To identify the protein signatures specific for PCa, protein expression profiling of 8 PCa patients, 12 BPH patients and 10 healthy males was carried out using LC-MS/MS. This was followed by validating relative expression levels of proteins present in urine among all the patients using quantitative real time-PCR. This was followed by validating relative expression levels of proteins present in urine among all the patients using quantitative real time-PCR. This approach revealed that significant the down-regulation of Fibronectin and TP53INP2 was a characteristic event among PCa patients. Fibronectin mRNA down-regulation, was identified as offering improved specificity (50%) over PSA, albeit with a slightly lower although still acceptable sensitivity (75%) for detecting PCa. As for TP53INP2 on the other hand, its down-regulation was moderately sensitive (75%), identifying many patients with PCa, but was entirely non-specific (7%), designating many of the benign samples as malignant and being unable to accurately identify more than one negative.