Chromosomal rearrangements and genetic structure at different evolutionary levels of the Sorex araneus group.

Robertsonian (Rb) fusions received large theoretical support for their role in speciation, but empirical evidence is often lacking. Here, we address the role of Rb rearrangements on the genetic differentiation of the karyotypically diversified group of shrews, Sorex araneus. We compared genetic structure between 'rearranged' and 'common' chromosomes in pairwise comparisons of five karyotypic taxa of the group. Considering all possible comparisons, we found a significantly greater differentiation at rearranged chromosomes, supporting the role of chromosomal rearrangements in the general genetic diversification of this group. Intertaxa structure and distance were larger across rearranged chromosomes for most of the comparisons, although these differences were not significant. This last result could be explained by the large variance observed among microsatellite-based estimates. The differences observed among the pairs of taxa analysed support the role of both the hybrid karyotypic complexity and the level of evolutionary divergence.

A hybrid zone with coincident clines for autosomal and sex-specific markers in the Sorex araneus group.

In hybrid zones, endogenous counter-selection of hybrids is usually first expressed as reduced fertility or viability in hybrids of the heterogametic sex, a mechanism known as Haldane's rule. This phenomenon often leads to a differential of gene flow between sex-linked markers. Here, we address the possibility of a differential gene flow for Y chromosome, mtDNA and autosomal markers across the hybrid zone between the genetically and chromosomally well-differentiated species Sorex antinorii and Sorex araneus race Vaud. Intermarker comparison clearly revealed coincidental centre and very abrupt clines for all three types of markers. The overall level of genetic differentiation between the two species must be strong enough to hinder asymmetric introgression. Cyto-nuclear mismatches were also observed in the centre of hybrid zone. The significantly lower number of mismatches observed in males than in females possibly results from Y chromosome-mtDNA interactions. Results are compared with those previously reported in another hybrid zone between S. antinori and S. araneus race Cordon.

Isotopic variation across the Audubon's-myrtle warbler hybrid zone.

Differences in seasonal migratory behaviours are thought to be an important component of reproductive isolation in many organisms. Stable isotopes have been used with success in estimating the location and qualities of disjunct breeding and wintering areas. However, few studies have used isotopic data to estimate the movements of hybrid offspring in species that form hybrid zones. Here, we use stable hydrogen to estimate the wintering locations and migratory patterns of two common and widespread migratory birds, Audubon's (Setophaga auduboni) and myrtle (S. coronata) warblers, as well as their hybrids. These two species form a narrow hybrid zone with extensive interbreeding in the Rocky Mountains of British Columbia and Alberta, Canada, which has been studied for over four decades. Isotopes in feathers grown on the wintering grounds or early on migration reveal three important patterns: (1) Audubon's and myrtle warblers from allopatric breeding populations winter in isotopically different environments, consistent with band recovery data and suggesting that there is a narrow migratory transition between the two species, (2) most hybrids appear to overwinter in the south-eastern USA, similar to where myrtle warblers are known to winter, and (3) some hybrid individuals, particularly those along the western edge of the hybrid zone, show Audubon's-like isotopic patterns. These data suggest there is a migratory divide between these two species, but that it is not directly coincident with the centre of the hybrid zone in the breeding range. We interpret these findings and discuss them within the context of previous research on hybrid zones, speciation and migratory divides.

Evolutionary genetics of arbuscular mycorrhizal fungi - causes and consequences of multiple genomes in Glomus intraradices

Résumé Les champignons endomycorhiziens arbusculaires (CEA) forment des symbioses avec la plupart des plantes terrestres. Les CEA influencent la croissance des plantes et la biodiversité. Ils sont supposés avoir évolué de manière asexuée pendant au moins 400 millions d'années et aucune diversification morphologique majeure n'a été constatée. Pour ces raisons, les CEA sont considérés comme d'anciens asexués. Très peu d'espèces sont connues actuellement. Les individus de ces champignons contiennent des noyaux génétiquement différents dans un cytoplasme continu. La signification évolutive, la variabilité et la maintenance des génomes multiples au sein des individus sont inconnues. Ce travail a démontré qu'une population du CEA Glomus intraradices est génétiquement très variable. Nous avons conclu que les plantes hôtes plutôt que la différenciation géographique devraient être responsables de cette grande diversité. Puis nous avons cherché l'existence de recombinaison entre génotypes dans une population. Nous avons détecté un groupe recombinant au sein de la population, ce qui met en doute l'état d'anciens asexués des CEA. Nous avons également détecté l'occurrence de fusions d'hyphes et l'échange de noyaux entre isolats génétiquement différents. La descendance hybride issue de cet échange était viable et distincte phénotypiquement des isolats parentaux. En résumé, ce travail identifie des événements cruciaux dans le cycle de vie des CEA qui ont le potentiel d'influencer l'évolution de génomes multiples. L'étude des conséquences de ces événements sur les interactions avec les plantes hôtes pourrait éclaircir significativement la compréhension de la symbiose entre plantes et CEA. Abstract Arbuscular mycorrhizal fungi (AMF) are important symbionts of most land plants. AMF influence plant growth and biodiversity. Very few extant species are described. AMF are thought to have evolved asexually for at least 400 million years and no major morphological diversification has occurred. Due to these reasons, they were termed `ancient asexuals'. Fungal individuals harbour genetically different nuclei in a continuous cytoplasm. The variability, maintenance and evolutionary significance of multiple genomes within individuals are unknown. This work showed that a population of the AMF Glomus intraradices harbours very high genetic diversity. We concluded that host plants rather than geographic differentiation were responsible for this diversity. Furthermore, we investigated whether recombination occurred among genotypes of a G. intraradices population. The identification of a core group of recombining genotypes in the population refutes the assumption of ancient asexuality in AMF. We found that genetically different isolates can form hyphal fusions and exchange nuclei. The hybrid progeny produced by the exchange was viable and phenotypically distinct from the parental isolates. Taken together, this work provided evidence for key events in the AMF life cycle, that influence the evolution of multiple genomes. Studying the consequences of these events on the interaction with host plants may significantly further the understanding of the AMF-plant symbiosis.

Adaptive approach heuristics for the generalized assignment problem

The Generalized Assignment Problem consists in assigning a setof tasks to a set of agents with minimum cost. Each agent hasa limited amount of a single resource and each task must beassigned to one and only one agent, requiring a certain amountof the resource of the agent. We present new metaheuristics forthe generalized assignment problem based on hybrid approaches.One metaheuristic is a MAX-MIN Ant System (MMAS), an improvedversion of the Ant System, which was recently proposed byStutzle and Hoos to combinatorial optimization problems, and itcan be seen has an adaptive sampling algorithm that takes inconsideration the experience gathered in earlier iterations ofthe algorithm. Moreover, the latter heuristic is combined withlocal search and tabu search heuristics to improve the search.A greedy randomized adaptive search heuristic (GRASP) is alsoproposed. Several neighborhoods are studied, including one basedon ejection chains that produces good moves withoutincreasing the computational effort. We present computationalresults of the comparative performance, followed by concludingremarks and ideas on future research in generalized assignmentrelated problems.

Evolving team compositions by agent swapping

Optimizing collective behavior in multiagent systems requires algorithms to find not only appropriate individual behaviors but also a suitable composition of agents within a team. Over the last two decades, evolutionary methods have emerged as a promising approach for the design of agents and their compositions into teams. The choice of a crossover operator that facilitates the evolution of optimal team composition is recognized to be crucial, but so far, it has never been thoroughly quantified. Here, we highlight the limitations of two different crossover operators that exchange entire agents between teams: restricted agent swapping (RAS) that exchanges only corresponding agents between teams and free agent swapping (FAS) that allows an arbitrary exchange of agents. Our results show that RAS suffers from premature convergence, whereas FAS entails insufficient convergence. Consequently, in both cases, the exploration and exploitation aspects of the evolutionary algorithm are not well balanced resulting in the evolution of suboptimal team compositions. To overcome this problem, we propose combining the two methods. Our approach first applies FAS to explore the search space and then RAS to exploit it. This mixed approach is a much more efficient strategy for the evolution of team compositions compared to either strategy on its own. Our results suggest that such a mixed agent-swapping algorithm should always be preferred whenever the optimal composition of individuals in a multiagent system is unknown.

Clinal variation in a brown lemur (Eulemur spp.) hybrid zone: Combining morphological, genetic and climatic data to examine stability.

Studies of hybrid zones can inform our understanding of reproductive isolation and speciation. Two species of brown lemur (Eulemur rufifrons and E. cinereiceps) form an apparently stable hybrid zone in the Andringitra region of south-eastern Madagascar. The aim of this study was to identify factors that contribute to this stability. We sampled animals at 11 sites along a 90-km transect through the hybrid zone and examined variation in 26 microsatellites, the D-loop region of mitochondrial DNA, six pelage and nine morphological traits; we also included samples collected in more distant allopatric sites. Clines in these traits were noncoincident, and there was no increase in either inbreeding coefficients or linkage disequilibrium at the centre of the zone. These results could suggest that the hybrid zone is maintained by weak selection against hybrids, conforming to either the tension zone or geographical selection-gradient model. However, a closer examination of clines in pelage and microsatellites indicates that these clines are not sigmoid or stepped in shape but instead plateau at their centre. Sites within the hybrid zone also occur in a distinct habitat, characterized by greater seasonality in precipitation and lower seasonality in temperature. Together, these findings suggest that the hybrid zone may follow the bounded superiority model, with exogenous selection favouring hybrids within the transitional zone. These findings are noteworthy, as examples supporting the bounded superiority model are rare and may indicate a process of ecologically driven speciation without geographical isolation.

Line search multilevel optimization as computational methods for dense optical flow

We evaluate the performance of different optimization techniques developed in the context of optical flow computation with different variational models. In particular, based on truncated Newton methods (TN) that have been an effective approach for large-scale unconstrained optimization, we de- velop the use of efficient multilevel schemes for computing the optical flow. More precisely, we evaluate the performance of a standard unidirectional mul- tilevel algorithm - called multiresolution optimization (MR/OPT), to a bidrec- tional multilevel algorithm - called full multigrid optimization (FMG/OPT). The FMG/OPT algorithm treats the coarse grid correction as an optimiza- tion search direction and eventually scales it using a line search. Experimental results on different image sequences using four models of optical flow com- putation show that the FMG/OPT algorithm outperforms both the TN and MR/OPT algorithms in terms of the computational work and the quality of the optical flow estimation.

A framework for hybrid simulations of two-phase flow in porous media

Rough a global coarse problem. Although these techniques are usually employed for problems in which the fine-scale processes are described by Darcy's law, they can also be applied to pore-scale simulations and used as a mathematical framework for hybrid methods that couples a Darcy and pore scales. In this work, we consider a pore-scale description of fine-scale processes. The Navier-Stokes equations are numerically solved in the pore geometry to compute the velocity field and obtain generalized permeabilities. In the case of two-phase flow, the dynamics of the phase interface is described by the volume of fluid method with the continuum surface force model. The MsFV method is employed to construct an algorithm that couples a Darcy macro-scale description with a pore-scale description at the fine scale. The hybrid simulations results presented are in good agreement with the fine-scale reference solutions. As the reconstruction of the fine-scale details can be done adaptively, the presented method offers a flexible framework for hybrid modeling.

Genetic and karyotypic structure of a hybrid zone between the chromosomal races Cordon and Valais in the common shrew, Sorex araneus

Hybrid zones between genetically differentiated populations provide material to study evolutionary processes. Since the discovery of chromosomal races in Sorex araneus, contact zones have attracted attention of scientists. So far, studies on genetic markers in Sorex hybrid zones are missing. The acrocentric chromosomal race Cordon and the highly metacentric race Valais meet and hybridize at Les Houches in the Western Alps. On a transect through the hybrid zone, 273 shrews were caught at 15 localities over 4 years. Karyotype as well as the nuclear protein loci Alb and Pg were analyzed. F-st and F-is values were calculated by F-statistics. An analysis on pooled samples revealed the genetical differences between the hybridizing races as the only cause of population structuring. Genetical markers show dines with very strong frequency shifts at a mountain torrent, but behave differently through the zone. The performance of the torrent in maintaining the hybrid zone, selection against hybrids, possible assortative mating and linkage of the Valais Pg allele to a diagnostic chromosome arm, are discussed.

Detection and mapping of a lethal locus in a eucalyptus hybrid population

The objective of this work was to verify the existence of a lethal locus in a eucalyptus hybrid population, and to quantify the segregation distortion in the linkage group 3 of the Eucalyptus genome. A E. grandis x E. urophylla hybrid population, which segregates for rust resistance, was genotyped with 19 microsatellite markers belonging to linkage group 3 of the Eucalyptus genome. To quantify the segregation distortion, maximum likelihood (ML) models, specific to outbreeding populations, were used. These models consider the observed marker genotypes and the lethal locus viability as parameters. The ML solutions were obtained using the expectation‑maximization algorithm. A lethal locus in the linkage group 3 was verified and mapped, with high confidence, between the microssatellites EMBRA 189 e EMBRA 122. This lethal locus causes an intense gametic selection from the male side. Its map position is 25 cM from the locus which controls the rust resistance in this population.

Avian Evolutionary Genomics: Studies of Ficedula Flycatchers

In this thesis, different genetic tools are used to investigate both natural variation and speciation in the Ficedula flycatcher system: pied (Ficedula hypoleuca) and collared (F. albicollis) flycatchers. The molecular evolution of a gene involved in postnatal body growth, GH, has shown high degree of conservation at the mature protein between birds and mammals, whereas the variation observed in its signal peptide seems to be adaptive in pied flycatcher (I & II). Speciation is the process by which reproductive barriers to gene flow evolve between populations, and understanding the mechanisms involved in pre- and post-zygotic isolation have been investigated in Ficedula flycatchers. The Z chromosome have been suggested to be the hotspot for genes involved in speciation, thus sequencing of 13 Z-linked coding genes from the two species in allopatry and sympatry have been conducted (III). Surprisingly, the majority of Z-linked genes seemed to be highly conserved, suggesting instead a potential involvement of regulatory regions. Previous studies have shown that genes involved in hybrid fitness, female preferences and male plumage colouration are sex-linked. Hence, three pigmentation genes have been investigated: MC1R, AGRP, and TYRP1. Of these three genes, TYRP1 was identified as a strong candidate to be associated with black-brown plumage variation in sympatric populations, and hence is a strong candidate for a gene contributing to pre-zygotic isolation (IV). In sympatric areas, where pied and collared flycatchers have overlapping breeding areas, hybridization sometimes occurs leading to the production of unfit hybrids. By using a proteomic approach a novel expression pattern in hybrids was revealed compared to the parental species (V) and differentially expressed proteins subsequently identified by sequence similarity (VI). In conclusion, the Z chromosome appears to play an important role in flycatcher speciation, but probably not at the coding level. In addition the novel expression patterns might give new insights into the maladaptive hybrids.

ML estimator and hybrid beamformer for multipath and interference mitigation in GNSS receivers

This paper addresses the estimation of the code-phase(pseudorange) and the carrier-phase of the direct signal received from a direct-sequence spread-spectrum satellite transmitter. Thesignal is received by an antenna array in a scenario with interferenceand multipath propagation. These two effects are generallythe limiting error sources in most high-precision positioning applications.A new estimator of the code- and carrier-phases is derivedby using a simplified signal model and the maximum likelihood(ML) principle. The simplified model consists essentially ofgathering all signals, except for the direct one, in a component withunknown spatial correlation. The estimator exploits the knowledgeof the direction-of-arrival of the direct signal and is much simplerthan other estimators derived under more detailed signal models.Moreover, we present an iterative algorithm, that is adequate for apractical implementation and explores an interesting link betweenthe ML estimator and a hybrid beamformer. The mean squarederror and bias of the new estimator are computed for a numberof scenarios and compared with those of other methods. The presentedestimator and the hybrid beamforming outperform the existingtechniques of comparable complexity and attains, in manysituations, the Cramér–Rao lower bound of the problem at hand.

Normaalijakaumaan perustuva mutaatio-operaatio differentiaalievoluutioalgoritmiin

Evoluutioalgoritmit ovat viime vuosina osoittautuneet tehokkaiksi menetelmiksi globaalien optimointitehtävien ratkaisuun. Niiden vahvuutena on etenkin yleiskäyttöisyys ja kyky löytää globaali ratkaisu juuttumatta optimoitavan tavoitefunktion paikallisiin optimikohtiin. Tässä työssä on tavoitteena kehittää uusi, normaalijakaumaan perustuva mutaatio-operaatio differentiaalievoluutioalgoritmiin, joka on eräs uusimmista evoluutiopohjaisista optimointialgoritmeista. Menetelmän oletetaan vähentävän entisestään sekä populaation ennenaikaisen suppenemisen, että algoritmin tilojen juuttumisen riskiä ja se on teoreettisesti osoitettavissa suppenevaksi. Tämä ei päde alkuperäisen differentiaalievoluution tapauksessa, koska on voitu osoittaa, että sen tilanmuutokset voivat pienellä todennäköisyydellä juuttua. Työssä uuden menetelmän toimintaa tarkastellaan kokeellisesti käyttäen testiongelmina monirajoiteongelmia. Rajoitefunktioiden käsittelyyn käytetään Jouni Lampisen kehittämää, Pareto-optimaalisuuden periaatteeseen perustuvaa menetelmää. Samalla saadaan kerättyä lisää kokeellista näyttöä myös tämän menetelmän toiminnasta. Kaikki käytetyt testiongelmat kyettiin ratkaisemaan sekä alkuperäisellä differentiaalievoluutiolla, että uutta mutaatio-operaatiota käyttävällä versiolla. Uusi menetelmä osoittautui kuitenkin luotettavammaksi sellaisissa tapauksissa, joissa alkuperäisellä algoritmilla oli vaikeuksia. Lisäksi useimmat ongelmat kyettiin ratkaisemaan luotettavasti pienemmällä populaation koolla kuin alkuperäistä differentiaalievoluutiota käytettäessä. Uuden menetelmän käyttö myös mahdollistaa paremmin sellaisten kontrolliparametrien käytön, joilla hausta saadaan rotaatioinvariantti. Laskennallisesti uusi menetelmä on hieman alkuperäistä differentiaalievoluutiota raskaampi ja se tarvitsee yhden kontrolliparametrin enemmän. Uusille kontrolliparametreille määritettiin kuitenkin mahdollisimman yleiskäyttöiset arvot, joita käyttämällä on mahdollista ratkaista suuri joukko erilaisia ongelmia.