Bounding Run-Times of Local Adiabatic Algorithms

A common trick for designing faster quantum adiabatic algorithms is to apply the adiabaticity condition locally at every instant. However it is often difficult to determine the instantaneous gap between the lowest two eigenvalues, which is an essential ingredient in the adiabaticity condition. In this paper we present a simple linear algebraic technique for obtaining a lower bound on the instantaneous gap even in such a situation. As an illustration, we investigate the adiabatic un-ordered search of van Dam et al. [17] and Roland and Cerf [15] when the non-zero entries of the diagonal final Hamiltonian are perturbed by a polynomial (in log N, where N is the length of the unordered list) amount. We use our technique to derive a bound on the running time of a local adiabatic schedule in terms of the minimum gap between the lowest two eigenvalues.

Molecular Genetics of Age-related Macular Degeneration

Age-related macular degeneration (AMD; OMIM # 603075) is an eye disease of the elderly, signs of which appear after the age of 50. In the Western world it is a leading cause of permanent visual loss with a prevalence of 8.5% in persons under 54 years of age and of 37% in persons over 75 years of age. Early forms of AMD may be asymptomatic, but in the late forms usually a central scotoma in the visual field follows severely complicating daily tasks. Smoking, age, and genetic predisposition are known risk factors for AMD. Until recently no true susceptibility genes had been identified though the composition of drusen deposits, the hallmarks of AMD, has suggested that the complement system might play a role in the pathogenesis of AMD. When four groups reported in March 2005, that, on chromosome 1q32, a Y402H variant in the complement factor H (CFH) gene confers risk for AMD in independent Caucasian samples, a new period in the field of genetic research of AMD started. CFH is a key regulator of the complement system. Thus, it is logical to speculate, that it plays a role in the pathogenesis of AMD. We performed a case-control association study to analyse whether the CFH Y402H variant contain a risk for AMD in the Finnish population. Although the population of Finland represents a genetic isolate, the CFH Y402H polymorphism was associated with AMD also in our patient sample with similar risk allele frequencies as in the other Caucasian populations. We further evaluated the effects of this variant, but no association between lesion subtype (predominantly classic, minimally classic or occult lesion) or lesion size of neovascular AMD and the CFH Y402H variant was detected. Neither did the variant have an effect on the photodynamic therapy (PDT) outcome. The patients that respond to PDT carried the risk genotype as frequently as those who did not respond, and no difference was found in the number of PDT sessions needed in patients with or without the risk genotypes of CFH Y402H. Functional analyses, however, showed that the binding of C-reactive protein (CRP) to CFH was significantly reduced in patients with the risk genotype of Y402H. In the past two years, the LOC387715/ high-temperature requirement factor A1 (HTRA1) locus on 10q26 has also been repeatedly associated with AMD in several populations. The recent discovery of the LOC387715 protein on the mitochondrial outer membrane suggests that the LOC387715 gene, not HTRA1, is the true predisposing gene in this region, although its biological function is still unknown. In our Finnish patient material, patients with AMD carried the A69S risk genotype of LOC387715 more frequently than the controls. Also, for the first time, an interaction between the CFH Y402H and the LOC387715 A69S variants was found. The most recently detected susceptibilty gene of AMD, the complement component 3 (C3) gene, encodes the central component of the complement system, C3. In our Finnish sample, an additive gene effect for the C3 locus was detected, though weaker than the effects for the two main loci, CFH and LOC387715. Instead, the hemicentin-1 or the elongation of very long chain fatty acids-like 4 genes that have also been suggested as candidate genes for AMD did not carry a risk for AMD in the Finnish population. This was the first series of molecular genetic study of AMD in Finland. We showed that two common risk variants, CFH Y402H and LOC387715 A69S, represent a high risk of AMD also in the isolated Finnish population, and furthermore, that they had a statistical interaction. It was demonstrated that the CFH Y402H risk genotype affects the binding of CFH to CRP thus suggesting that complement indeed plays an important role in the pathogenesis of AMD.

Linear time algorithms for Abelian group isomorphism and related problems

We consider the problem of determining if two finite groups are isomorphic. The groups are assumed to be represented by their multiplication tables. We present an O(n) algorithm that determines if two Abelian groups with n elements each are isomorphic. This improves upon the previous upper bound of O(n log n) [Narayan Vikas, An O(n) algorithm for Abelian p-group isomorphism and an O(n log n) algorithm for Abelian group isomorphism, J. Comput. System Sci. 53 (1996) 1-9] known for this problem. We solve a more general problem of computing the orders of all the elements of any group (not necessarily Abelian) of size n in O(n) time. Our algorithm for isomorphism testing of Abelian groups follows from this result. We use the property that our order finding algorithm works for any group to design a simple O(n) algorithm for testing whether a group of size n, described by its multiplication table, is nilpotent. We also give an O(n) algorithm for determining if a group of size n, described by its multiplication table, is Abelian. (C) 2007 Elsevier Inc. All rights reserved.

Discrete parameter simulation optimization algorithms with applications to admission control with dependent service times

We propose certain discrete parameter variants of well known simulation optimization algorithms. Two of these algorithms are based on the smoothed functional (SF) technique while two others are based on the simultaneous perturbation stochastic approximation (SPSA) method. They differ from each other in the way perturbations are obtained and also the manner in which projections and parameter updates are performed. All our algorithms use two simulations and two-timescale stochastic approximation. As an application setting, we consider the important problem of admission control of packets in communication networks under dependent service times. We consider a discrete time slotted queueing model of the system and consider two different scenarios - one where the service times have a dependence on the system state and the other where they depend on the number of arrivals in a time slot. Under our settings, the simulated objective function appears ill-behaved with multiple local minima and a unique global minimum characterized by a sharp dip in the objective function in a small region of the parameter space. We compare the performance of our algorithms on these settings and observe that the two SF algorithms show the best results overall. In fact, in many cases studied, SF algorithms converge to the global minimum.

Hybrid algorithms for power system unit commitment

Four hybrid algorithms has been developed for the solution of the unit commitment problem. They use simulated annealing as one of the constituent techniques, and produce lower cost schedules; two of them have less overhead than other soft computing techniques. They are also more robust to the choice of parameters. A special technique avoids the generating of infeasible schedules, and thus reduces computation time.

Pharmacogenetics of SLCO1B1: Population genetics and effect on statins

Kohonneiden kolesterolipitoisuuksien alentamisessa käytettävien statiinien hyödyt sydän- ja verisuonisairauksien estossa on vahvasti osoitettu ja niiden käyttö on niin Suomessa kuin muuallakin maailmassa kasvanut voimakkaasti – Suomessa statiininkäyttäjiä on noin 600 000. Statiinilääkitys on pitkäaikaisessakin käytössä melko hyvin siedetty, mutta yleisimpinä haittavaikutuksina voi ilmetä lihasheikkoutta, -kipua ja -kramppeja, jotka voivat edetä jopa henkeä uhkaavaksi lihasvaurioksi. Lihashaittariski suurenee suhteessa statiiniannokseen ja plasman statiinipitoisuuksiin. Statiinien plasmapitoisuuksissa, tehossa ja haittavaikutusten ilmenemisessä on suuria potilaskohtaisia eroja. SLCO1B1-geenin koodaama OATP1B1-kuljetusproteiini kuljettaa monia elimistön omia aineita ja lääkeaineita verenkierrosta solukalvon läpi maksasoluun, mm. statiineja, joiden kolesterolia alentava vaikutus ja poistuminen elimistöstä tapahtuvat pääosin maksassa. Erään SLCO1B1-geenin nukleotidimuutoksen (c.521T>C) tiedetään heikentävän OATP1B1:n kuljetustehoa. Tässä väitöskirjatyössä selvitettiin SLCO1B1-geenin perinnöllistä muuntelua suomalaisilla ja eri väestöissä maailmanlaajuisesti. Lisäksi selvitettiin SLCO1B1:n muunnosten vaikutusta eri statiinien pitoisuuksiin (farmakokinetiikka) ja vaikutuksiin (farmakodynamiikka) sekä kolesteroliaineenvaihduntaan. Näihin tutkimuksiin valittiin SLCO1B1-genotyypin perusteella terveitä vapaaehtoisia koehenkilöitä, joille annettiin eri päivinä kerta-annos kutakin tutkittavaa statiinia: fluvastatiinia, pravastatiinia, simvastatiinia, rosuvastatiinia ja atorvastatiinia. Verinäytteistä määritettiin plasman statiinien ja niiden aineenvaihduntatuotteiden sekä kolesterolin ja sen muodostumista ja imeytymistä kuvaavien merkkiaineiden pitoisuuksia. Toiminnallisesti merkittävien SLCO1B1-geenimuunnosten esiintyvyydessä todettiin suuria eroja eri väestöjen välillä. Suomalaisilla SLCO1B1 c.521TC-genotyypin (geenimuunnos toisessa vastinkromosomissa) esiintyvyys oli noin 32 % ja SLCO1B1 c.521CC-genotyypin (geenimuunnos molemmissa vastinkromosomeissa) esiintyvyys noin 4 %. Globaalisti geenimuunnosten esiintyvyys korreloi maapallon leveyspiirien kanssa siten, että matalaan transportteriaktiivisuuteen johtavat muunnokset olivat yleisimpiä pohjoisessa ja korkeaan aktiivisuuteen johtavat päiväntasaajan lähellä asuvilla väestöillä. SLCO1B1-genotyypillä oli merkittävä vaikutus statiinien plasmapitoisuksiin lukuun ottamatta fluvastatiinia. Simvastatiinihapon plasmapitoisuudet olivat keskimäärin 220 %, atorvastatiinin 140 %, pravastatiinin 90 % ja rosuvastatiinin 70 % suuremmat c.521CC-genotyypin omaavilla koehenkilöillä verrattuna normaalin c.521TT-genotyypin omaaviin. Genotyypillä ei ollut merkittävää vaikutusta minkään statiinin tehoon tässä kerta-annostutkimuksessa, mutta geenimuunnoksen kantajilla perustason kolesterolisynteesinopeus oli suurempi. Tulokset osoittavat, että SLCO1B1 c.521T>C geenimuunnos on varsin yleinen suomalaisilla ja muilla ei-afrikkalaisilla väestöillä. Tämä geenimuunnos voi altistaa erityisesti simvastatiinin, mutta myös atorvastatiinin, pravastatiinin ja rosuvastatiinin, aiheuttamille lihashaitoille suurentamalla niiden plasmapitoisuuksia. SLCO1B1:n geenimuunnoksen testaamista voidaan tulevaisuudessa käyttää apuna valittaessa sopivaa statiinilääkitystä ja -annosta potilaalle, ja näin parantaa sekä statiinihoidon turvallisuutta että tehoa.

New algorithms of the Q-learning type

We propose two algorithms for Q-learning that use the two-timescale stochastic approximation methodology. The first of these updates Q-values of all feasible state–action pairs at each instant while the second updates Q-values of states with actions chosen according to the ‘current’ randomized policy updates. A proof of convergence of the algorithms is shown. Finally, numerical experiments using the proposed algorithms on an application of routing in communication networks are presented on a few different settings.

OFDM-MAC algorithms and their impact on TCP performance in next generation mobile networks

Next generation wireless systems employ Orthogonal frequency division multiplexing (OFDM) physical layer owing to the high data rate transmissions that are possible without increase in bandwidth. While TCP performance has been extensively studied for interaction with link layer ARQ, little attention has been given to the interaction of TCP with MAC layer. In this work, we explore cross-layer interactions in an OFDM based wireless system, specifically focusing on channel-aware resource allocation strategies at the MAC layer and its impact on TCP congestion control. Both efficiency and fairness oriented MAC resource allocation strategies were designed for evaluating the performance of TCP. The former schemes try to exploit the channel diversity to maximize the system throughput, while the latter schemes try to provide a fair resource allocation over sufficiently long time duration. From a TCP goodput standpoint, we show that the class of MAC algorithms that incorporate a fairness metric and consider the backlog outperform the channel diversity exploiting schemes.

New approximation algorithms for minimum cycle bases of graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time 0(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time 0(n(3+2/k)), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega)) bound. We also present a 2-approximation algorithm with O(m(omega) root n log n) expected running time, a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Parametrized actor-critic algorithms for finite-horizon MDPs

Due to their non-stationarity, finite-horizon Markov decision processes (FH-MDPs) have one probability transition matrix per stage. Thus the curse of dimensionality affects FH-MDPs more severely than infinite-horizon MDPs. We propose two parametrized 'actor-critic' algorithms to compute optimal policies for FH-MDPs. Both algorithms use the two-timescale stochastic approximation technique, thus simultaneously performing gradient search in the parametrized policy space (the 'actor') on a slower timescale and learning the policy gradient (the 'critic') via a faster recursion. This is in contrast to methods where critic recursions learn the cost-to-go proper. We show w.p 1 convergence to a set with the necessary condition for constrained optima. The proposed parameterization is for FHMDPs with compact action sets, although certain exceptions can be handled. Further, a third algorithm for stochastic control of stopping time processes is presented. We explain why current policy evaluation methods do not work as critic to the proposed actor recursion. Simulation results from flow-control in communication networks attest to the performance advantages of all three algorithms.

Ultra high throughput sequencing excludes MDH1 as candidate gene for RP28-linked retinitis pigmentosa

Purpose: Mutations in IDH3B, an enzyme participating in the Krebs cycle, have recently been found to cause autosomal recessive retinitis pigmentosa (arRP). The MDH1 gene maps within the RP28 arRP linkage interval and encodes cytoplasmic malate dehydrogenase, an enzyme functionally related to IDH3B. As a proof of concept for candidate gene screening to be routinely performed by ultra high throughput sequencing (UHTs), we analyzed MDH1 in a patient from each of the two families described so far to show linkage between arRP and RP28. Methods: With genomic long-range PCR, we amplified all introns and exons of the MDH1 gene (23.4 kb). PCR products were then sequenced by short-read UHTs with no further processing. Computer-based mapping of the reads and mutation detection were performed by three independent software packages. Results: Despite the intrinsic complexity of human genome sequences, reads were easily mapped and analyzed, and all algorithms used provided the same results. The two patients were homozygous for all DNA variants identified in the region, which confirms previous linkage and homozygosity mapping results, but had different haplotypes, indicating genetic or allelic heterogeneity. None of the DNA changes detected could be associated with the disease. Conclusions: The MDH1 gene is not the cause of RP28-linked arRP. Our experimental strategy shows that long-range genomic PCR followed by UHTs provides an excellent system to perform a thorough screening of candidate genes for hereditary retinal degeneration.