A study of the time complexity of an Elitist Genetic Algorithm used for associating optical observations of MEO and GEO Space Debris

Currently several thousands of objects are being tracked in the MEO and GEO regions through optical means. The problem faced in this framework is that of Multiple Target Tracking (MTT). In this context both the correct associations among the observations, and the orbits of the objects have to be determined. The complexity of the MTT problem is defined by its dimension S. Where S stands for the number of ’fences’ used in the problem, each fence consists of a set of observations that all originate from dierent targets. For a dimension of S ˃ the MTT problem becomes NP-hard. As of now no algorithm exists that can solve an NP-hard problem in an optimal manner within a reasonable (polynomial) computation time. However, there are algorithms that can approximate the solution with a realistic computational e ort. To this end an Elitist Genetic Algorithm is implemented to approximately solve the S ˃ MTT problem in an e cient manner. Its complexity is studied and it is found that an approximate solution can be obtained in a polynomial time. With the advent of improved sensors and a heightened interest in the problem of space debris, it is expected that the number of tracked objects will grow by an order of magnitude in the near future. This research aims to provide a method that can treat the correlation and orbit determination problems simultaneously, and is able to e ciently process large data sets with minimal manual intervention.

A transposable element insertion in APOB causes cholesterol deficiency in Holstein cattle

Cholesterol deficiency, a new autosomal recessive inherited genetic defect in Holstein cattle, has been recently reported to have an influence on the rearing success of calves. The affected animals show unresponsive diarrhea accompanied by hypocholesterolemia and usually die within the first weeks or months of life. Here, we show that whole genome sequencing combined with the knowledge about the pedigree and inbreeding status of a livestock population facilitates the identification of the causative mutation. We resequenced the entire genomes of an affected calf and a healthy partially inbred male carrying one copy of the critical 2.24-Mb chromosome 11 segment in its ancestral state and one copy of the same segment with the cholesterol deficiency mutation. We detected a single structural variant, homozygous in the affected case and heterozygous in the non-affected carrier male. The genetic makeup of this key animal provides extremely strong support for the causality of this mutation. The mutation represents a 1.3kb insertion of a transposable LTR element (ERV2-1) in the coding sequence of the APOB gene, which leads to truncated transcripts and aberrant splicing. This finding was further supported by RNA sequencing of the liver transcriptome of an affected calf. The encoded apolipoprotein B is an essential apolipoprotein on chylomicrons and low-density lipoproteins, and therefore, the mutation represents a loss of function mutation similar to autosomal recessive inherited familial hypobetalipoproteinemia-1 (FHBL1) in humans. Our findings provide a direct gene test to improve selection against this deleterious mutation in Holstein cattle.

Molecular and genetic analyses of Fgf signaling during cardiac outflow tract development

Epithelial-mesenchymal tissue interactions regulate the development of derivatives of the caudal pharyngeal arches (PAs) to govern the ultimate morphogenesis of the aortic arch and outflow tract (OFT) of the heart. Disruption of these signaling pathways is thought to contribute to the pathology of a significant proportion of congenital cardiovascular defects in humans. In this study, I tested whether Fibroblast Growth Factor 15 (Fgf15), a secreted signaling molecule expressed within the PAs, is an extracellular mediator of tissue interactions during PA and OFT development. Analyses of Fgf15−/− mouse embryonic hearts revealed abnormalities primarily localized to the OFT, correlating with aberrant cardiac neural crest cell behavior. The T-box-containing transcription factor Tbx1 has been implicated in the cardiovascular defects associated with the human 22q11 Deletion Syndromes, and regulates the expression of other Fgf family members within the mouse PAs. However, expression and genetic interaction studies incorporating mice deficient for Tbx1, its upstream regulator, Sonic Hedgehog (Shh), or its putative downstream effector, Fgf8, indicated that Fgf15 functions during OFT development in a manner independent of these factors. Rather, analyses of compound mutant mice indicated that Fgf15 and Fgf9, an additional Fgf family member expressed within the PAs, genetically interact, providing insight into the factors acting in conjunction with Fgf15 during OFT development. Finally, in an effort to further characterize this Fgf15-mediated developmental pathway, promoter deletion analyses were employed to isolate a 415bp sequence 7.1Kb 5′ to the Fgf15 transcription start site both necessary and sufficient to drive reporter gene expression within the epithelium of the PAs. Sequence comparisons among multiple mammalian species facilitated the identification of evolutionarily conserved potential trans-acting factor binding sites within this fragment. Subsequent studies will investigate the molecular pathway(s) through which Fgf15 functions via identification of factors that bind to this element to govern Fgf15 gene expression. Furthermore, targeted deletion of this element will establish the developmental requirement for pharyngeal epithelium-derived Fgf15 signaling function. Taken as a whole, these data demonstrate that Fgf15 is a component of a novel, Tbx1-independent molecular pathway, functioning within the PAs in a manner cooperative with Fgf9, required for proper development of the cardiac OFT. ^

Identification of genetic variation influencing apolipoprotein E levels: Follow-up of genome-wide linkage scans in the GENOA study

Apolipoprotein E (ApoE) plays a major role in the metabolism of high density and low density lipoproteins (HDL and LDL). Its common protein isoforms (E2, E3, E4) are risk factors for coronary artery disease (CAD) and explain between 16 to 23% of the inter-individual variation in plasma apoE levels. Linkage analysis has been completed for plasma apoE levels in the GENOA study (Genetic Epidemiology Network of Atherosclerosis). After stratification of the population by lipoprotein levels and body mass index (BMI) to create more homogeneity with regard to biological context for apoE levels, Hispanic families showed significant linkage on chromosome 17q for two strata (LOD=2.93 at 104 cM for a low cholesterol group, LOD=3.04 at 111 cM for a low cholesterol, high HDLC group). Replication of 17q linkage was observed for apoB and apoE levels in the unstratified Hispanic and African-American populations, and for apoE levels in African-American families. Replication of this 17q linkage in different populations and strata provides strong support for the presence of gene(s) in this region with significant roles in the determination of inter-individual variation in plasma apoE levels. Through a positional and functional candidate gene approach, ten genes were identified in the 17q linked region, and 62 polymorphisms in these genes were genotyped in the GENOA families. Association analysis was performed with FBAT, GEE, and variance-component based tests followed by conditional linkage analysis. Association studies with partial coverage of TagSNPs in the gene coding for apolipoprotein H (APOH) were performed, and significant results were found for 2 SNPs (APOH_20951 and APOH_05407) in the Hispanic low cholesterol strata accounting for 3.49% of the inter-individual variation in plasma apoE levels. Among the other candidate genes, we identified a haplotype block in the ACE1 gene that contains two major haplotypes associated with apoE levels as well as total cholesterol, apoB and LDLC levels in the unstratified Hispanic population. Identifying genes responsible for the remaining 60% of inter-individual variation in plasma apoE level, will yield new insights into the understanding of genetic interactions involved in the lipid metabolism, and a more precise understanding of the risk factors leading to CAD. ^

Identification of genetic variants that influence atherosclerosis in young persons

Atherosclerosis is widely accepted as a complex genetic phenotype and is the usual cause of cardiovascular disease, the world’s leading killer. Genetic factors have been proven to be important risk contributors for atherosclerosis and much work has been done to identify promising candidates that might play a role in the development of atherosclerosis. It is well known that many independent replications are needed to unequivocally establish a valid genotype-phenotype association across different populations before the findings are extended to clinical settings and to the expensive follow-up studies designed to identify causal genetic variants. Aiming to replicate the association with atherosclerosis in the Pathobiological Determinants of Atherosclerosis in Youth (PDAY) study, we assessed the relationship of 32 atherosclerosis candidate SNPs to atherosclerosis in the PDAY cohort, consisting of AA and EA young people aged 15-34 years who died of non-medical causes. Two association studies, a whole sample study and a 1:1 matched case control study were performed by use of multiple linear regression and logistic regression analyses, respectively. For the whole sample association study, 32 SNPs among 2,650 individuals (1,369 AA and 1,281 EA) were tested for the association with six early atherosclerosis phenotypes: abdominal aorta fatty streaks, abdominal aorta raised lesions, right coronary artery fatty streaks, right coronary artery raised lesions, thoracic aorta fatty streaks, and thoracic aorta raised lesions. For the matched case-control association study, 337 case-control paired samples were included; cases were chosen with the highest total raised lesion scores from the studied population, while controls were randomly selected from individuals that had no raised lesions and matched to cases by age, gender and race. Sixteen SNPs in 13 genes were found to be significantly associated with atherosclerosis in at least one of the PDAY association studies. Among these 16 findings: eight SNPs (rs9579646, rs6053733, rs3849150, rs10499903, rs2148079, rs5073691, rs10116277, and rs17228212) successfully replicated previous results, six SNPs (rs17222814, rs10811661, rs7028570, rs7291467, rs16996148 and rs10401969) were reported as new findings exclusive to our study, the last two of the 16 SNPs, rs501120 and rs6922269, showed either intriguing or conflicting result. SNP rs17222814 in ALOX5AP and SNP rs3849150 in LRRC18 were consistently associated with atherosclerosis in both prior and the two PDAY association studies. SNP rs3849150 was also identified to be highly correlated with a non-synonymous coding SNP, rs17772611, which may damage the protein (polyphen score = 0.996), suggesting that SNP rs17772611 may be the causal functional variant.^ In conclusion, our study added more support for the association of these candidate genes with atherosclerosis. SNPs rs3849150 and rs17772611 of LRRC18, as well as SNP rs17222814 of ALOX5AP, were the most significant findings from our study, and may be ranked among the best for further study.^

Identification of genetic risk factors for cerebellar mutism in pediatric brain tumor patients

Following posterior fossa surgery for resection of childhood medulloblastoma and primitive neuroectodermal tumor (M/PNET), cerebellar mutism (CM) may develop. This is a condition of absent or diminished speech in a conscious patient with no evidence of oral apraxia, which can be accompanied by other symptoms of the posterior fossa syndrome complex, which includes ataxia and hypotonia. Little is known about the etiology. Therefore, we conducted a SNP, gene, and pathway-level analysis to assess the role of host genetic variation on the risk of CM in M/PNET subjects following treatment. Cases (n= 20) and controls (n= 53) were recruited from the Childhood Cancer Epidemiology and Prevention Center, in Houston, TX. DNA samples were genotyped using the Illumina Human 1M Quad SNP chip. Ten pathways were identified from logistic regression used to identify the marginal effect of each SNP on CM risk. The minP test was conducted to identify associations between SNPs categorized to genes and CM risk. Pathways were assessed to determine if there was a significant enrichment of genes in the pathway compared to all other pathways. There were 78 genes that reached the threshold of min P ≤0.05 in 948 genes. The Neurotoxicity pathway was the most significant pathway after adjusting for multiple comparisons (q=0.040 and q=0.005, using Fisher's exact test and a test of proportions, respectively). Most genes within the Neurotoxicity pathway that reached a threshold of minP ≤0.05 were known to have an apoptosis function, possibly inducing neuronal apoptosis in the dentatothalamocortical pathway, and may be important in CM etiology in this population. This is the first study to assess the potential role of genetic risk factors on CM. As an exploratory study, these results should be replicated in a larger sample. ^

A genetic characterization of {\it runt\/} activity during {\it Drosophila\/} embryogenesis

The Drosophila melanogaster gene runt encodes a novel transcriptional regulator that was originally identified on the basis of its key role in embryonic pattern formation. For my thesis I undertook a genetic analysis of runt activity to identify loci that interact with this unique transcriptional regulator. Specifically, I screened the genome with deficiencies for loci that interact with runt in a dose-dependent fashion during early embryogenesis. From this screen I discovered a vital dose-dependent interaction between runt and the achaete-scute complex (AS-C). The characterization of this interaction led to the exciting discovery of important roles for runt in sex determination and neurogenesis (Duffy and Gergen 1991, Duffy et al. 1991). I demonstrated that in sex determination runt is necessary for the normal transcriptional activation of the master sex-determining gene Sx1 and has all the properties of an X:A numerator element. I also showed that runt is required during the early stages of neurogenesis for the normal development of a subset of CNS ganglion mother cells and neurons. In addition, the screen, which focused on the identification and characterization of maternal loci that influence the activity of runt during segmentation, identified several new maternal loci, one of which affects the activity of the maternal posterior group genes on embryonic pattern formation. ^

Contemporary genetic, historical genetic and morphological data sets for the Yellow-tufted Honeyeater Lichenostomus melanops

Understanding the evolutionary history of threatened populations can improve their conservation management. Re-establishment of past but recent gene flow could re-invigorate threatened populations and replenish genetic diversity, necessary for population persistence. One of the four nominal subspecies of the common yellow-tufted honeyeater, Lichenostomus melanops cassidix, is critically endangered despite substantial conservation efforts over 55 years. Using a combination of morphometric, genetic and modelling approaches we tested for its evolutionary distinctiveness and conservation merit. We confirmed that cassidix has at least one morphometric distinction. It also differs genetically from the other subspecies in allele frequencies but not phylogenetically, implying that its evolution was recent. Modelling historical distribution supported the lack of vicariance and suggested a possibility of gene flow among subspecies at least since the late Pleistocene. Multi-locus coalescent analyses indicated that cassidix diverged from its common ancestor with neighbouring subspecies gippslandicus sometime from the mid-Pleistocene to the Holocene, and that it has the smallest historical effective population size of all subspecies. It appears that cassidix diverged from its ancestor with gippslandicus through a combination of drift and local selection. From patterns of genetic subdivision on two spatial scales and morphological variation we concluded that cassidix, gippslandicus and (melanops + meltoni) are diagnosable as subspecies. Low genetic diversity and effective population size of cassidix may translate to low genetic fitness and evolutionary potential, thus managed gene flow from gippslandicus is recommended for its recovery.

Impact of thermal stress on evolutionary trajectories of pathogen resistance in three-spined stickleback (Gasterosteus aculeatus), supplementary material

Background: Pathogens are a major regulatory force for host populations, especially under stressful conditions. Elevated temperatures may enhance the development of pathogens, increase the number of transmission stages, and can negatively influence host susceptibility depending on host thermal tolerance. As a net result, this can lead to a higher prevalence of epidemics during summer months. These conditions also apply to marine ecosystems, where possible ecological impacts and the population-specific potential for evolutionary responses to changing environments and increasing disease prevalence are, however, less known. Therefore, we investigated the influence of thermal stress on the evolutionary trajectories of disease resistance in three marine populations of three-spined sticklebacks Gasterosteus aculeatus by combining the effects of elevated temperature and infection with a bacterial strain of Vibrio sp. using a common garden experiment. Results: We found that thermal stress had an impact on fish weight and especially on survival after infection after only short periods of thermal acclimation. Environmental stress reduced genetic differentiation (QST) between populations by releasing cryptic within-population variation. While life history traits displayed positive genetic correlations across environments with relatively weak genotype by environment interactions (GxE), environmental stress led to negative genetic correlations across environments in pathogen resistance. This reversal of genetic effects governing resistance is probably attributable to changing environment-dependent virulence mechanisms of the pathogen interacting differently with host genotypes, i.e. GPathogenxGHostxE or (GPathogenxE)x(GHostxE) interactions, rather than to pure host genetic effects, i.e. GHostxE interactions. Conclusion: To cope with climatic changes and the associated increase in pathogen virulence, host species require wide thermal tolerances and pathogen-resistant genotypes. The higher resistance we found for some families at elevated temperatures showed that there is evolutionary potential for resistance to Vibrio sp. in both thermal environments. The negative genetic correlation of pathogen resistance between thermal environments, on the other hand, indicates that adaptation to current conditions can be a weak predictor for performance in changing environments. The observed feedback on selective gradients exerted on life history traits may exacerbate this effect, as it can also modify the response to selection for other vital components of fitness.

Grammar-Guided Evolutionary Construction of Bayesian networks

This paper proposes the EvoBANE system. EvoBANE automatically generates Bayesian networks for solving special-purpose problems. EvoBANE evolves a population of individuals that codify Bayesian networks until it finds near optimal individual that solves a given classification problem. EvoBANE has the flexibility to modify the constraints that condition the solution search space, self-adapting to the specifications of the problem to be solved. The system extends the GGEAS architecture. GGEAS is a general-purpose grammar-guided evolutionary automatic system, whose modular structure favors its application to the automatic construction of intelligent systems. EvoBANE has been applied to two classification benchmark datasets belonging to different application domains, and statistically compared with a genetic algorithm performing the same tasks. Results show that the proposed system performed better, as it manages different complexity constraints in order to find the simplest solution that best solves every problem.

Aerodynamic Optimization of High-Speed Trains Nose using a Genetic Algorithm and Artificial Neural Network

An aerodynamic optimization of the train aerodynamic characteristics in term of front wind action sensitivity is carried out in this paper. In particular, a genetic algorithm (GA) is used to perform a shape optimization study of a high-speed train nose. The nose is parametrically defined via Bézier Curves, including a wider range of geometries in the design space as possible optimal solutions. Using a GA, the main disadvantage to deal with is the large number of evaluations need before finding such optimal. Here it is proposed the use of metamodels to replace Navier-Stokes solver. Among all the posibilities, Rsponse Surface Models and Artificial Neural Networks (ANN) are considered. Best results of prediction and generalization are obtained with ANN and those are applied in GA code. The paper shows the feasibility of using GA in combination with ANN for this problem, and solutions achieved are included.

Clones Identification and Genetic Characterization of Garnacha Grapevine by Means of Different PCR-Derived Marker Systems

This study uses PCR-derived marker systems to investigate the extent and distribution of genetic variability of 53 Garnacha accessions coming from Italy, France and Spain. The samples studied include 28 Italian accessions (named Tocai rosso in Vicenza area; Alicante in Sicily and Elba island; Gamay perugino in Perugia province; Cannonau in Sardinia), 19 Spanish accessions of different types (named Garnacha tinta, Garnacha blanca, Garnacha peluda, Garnacha roja, Garnacha erguida, Garnacha roya) and 6 French accessions (named Grenache and Grenache noir). In order to verify the varietal identity of the samples, analyses based on 14 simple sequence repeat (SSR) loci were performed. The presence of an additional allele at ISV3 locus (151 bp) was found in four Tocai rosso accessions and in a Sardinian Cannonau clone, that are, incidentally, chimeras. In addition to microsatellite analysis, intravarietal variability study was performed using AFLP, SAMPL and M-AFLP molecular markers. AFLPs could discriminate among several Garnacha samples; SAMPLs allowed distinguishing few genotypes on the basis of their geographic origin, whereas M-AFLPs revealed plant-specific markers, differentiating all accessions. Italian samples showed the greatest variability among themselves, especially on the basis of their different provenance, while Spanish samples were the most similar, in spite of their morphological diversity.

Maximum Likelihood Estimation of Modal Parameters in Structures Using the Expectation Maximization Algorithm

This paper presents a time-domain stochastic system identification method based on maximum likelihood estimation (MLE) with the expectation maximization (EM) algorithm. The effectiveness of this structural identification method is evaluated through numerical simulation in the context of the ASCE benchmark problem on structural health monitoring. The benchmark structure is a four-story, two-bay by two-bay steel-frame scale model structure built in the Earthquake Engineering Research Laboratory at the University of British Columbia, Canada. This paper focuses on Phase I of the analytical benchmark studies. A MATLAB-based finite element analysis code obtained from the IASC-ASCE SHM Task Group web site is used to calculate the dynamic response of the prototype structure. A number of 100 simulations have been made using this MATLAB-based finite element analysis code in order to evaluate the proposed identification method. There are several techniques to realize system identification. In this work, stochastic subspace identification (SSI)method has been used for comparison. SSI identification method is a well known method and computes accurate estimates of the modal parameters. The principles of the SSI identification method has been introduced in the paper and next the proposed MLE with EM algorithm has been explained in detail. The advantages of the proposed structural identification method can be summarized as follows: (i) the method is based on maximum likelihood, that implies minimum variance estimates; (ii) EM is a computational simpler estimation procedure than other optimization algorithms; (iii) estimate more parameters than SSI, and these estimates are accurate. On the contrary, the main disadvantages of the method are: (i) EM algorithm is an iterative procedure and it consumes time until convergence is reached; and (ii) this method needs starting values for the parameters. Modal parameters (eigenfrequencies, damping ratios and mode shapes) of the benchmark structure have been estimated using both the SSI method and the proposed MLE + EM method. The numerical results show that the proposed method identifies eigenfrequencies, damping ratios and mode shapes reasonably well even in the presence of 10% measurement noises. These modal parameters are more accurate than the SSI estimated modal parameters.

Aerodynamic optimization of the ICE2 high-speed train nose using a genetic algorithm and metamodels

An aerodynamic optimization of the ICE 2 high-speed train nose in term of front wind action sensitivity is carried out in this paper. The nose is parametrically defined by Be?zier Curves, and a three-dimensional representation of the nose is obtained using thirty one design variables. This implies a more complete parametrization, allowing the representation of a real model. In order to perform this study a genetic algorithm (GA) is used. Using a GA involves a large number of evaluations before finding such optimal. Hence it is proposed the use of metamodels or surrogate models to replace Navier-Stokes solver and speed up the optimization process. Adaptive sampling is considered to optimize surrogate model fitting and minimize computational cost when dealing with a very large number of design parameters. The paper introduces the feasi- bility of using GA in combination with metamodels for real high-speed train geometry optimization.

Modeling, simulation and application of bacterial transduction in genetic algorithms

At present, all methods in Evolutionary Computation are bioinspired by the fundamental principles of neo-Darwinism, as well as by a vertical gene transfer. Virus transduction is one of the key mechanisms of horizontal gene propagation in microorganisms (e.g. bacteria). In the present paper, we model and simulate a transduction operator, exploring the possible role and usefulness of transduction in a genetic algorithm. The genetic algorithm including transduction has been named PETRI (abbreviation of Promoting Evolution Through Reiterated Infection). Our results showed how PETRI approaches higher fitness values as transduction probability comes close to 100%. The conclusion is that transduction improves the performance of a genetic algorithm, assuming a population divided among several sub-populations or ?bacterial colonies?.