@misc{3142, abstract = {Assembly of neuronal circuits is controlled by the sequential acquisition of neuronal subpopulation-specific identities at progressive developmental steps. Whereas neuronal features involved in initial phases of differentiation are already established at cell-cycle exit, recent findings, based mainly on work in the peripheral nervous system, suggest that the timely integration of signals encountered en route to targets and from the target region itself is essential to control late steps in connectivity. As neurons project towards their targets they require target-derived signals to establish mature axonal projections and acquire neuronal traits such as the expression of distinct combinations of neurotransmitters. Recent evidence presented in this review shows that this principle, of a signaling interplay between target-derived signals and neuronal cell bodies, is often mediated through transcriptional events and is evolutionarily conserved.}, author = {Simon Hippenmeyer and Kramer, Ina and Arber, Silvia}, booktitle = {Trends in Neurosciences}, number = {8}, pages = {482 -- 488}, publisher = {Elsevier}, title = {{Control of neuronal phenotype: What targets tell the cell bodies}}, doi = {10.1016/j.tins.2004.05.012}, volume = {27}, year = {2004}, } @article{3172, abstract = {The simultaneous multiple volume (SMV) approach in navigator-gated MRI allows the use of the whole motion range or the entire scan time for the reconstruction of final images by simultaneously acquiring different image volumes at different motion states. The motion tolerance range for each volume is kept small, thus SMV substantially increases the scan efficiency of navigator methods while maintaining the effectiveness of motion suppression. This article reports a general implementation of the SMV approach using a multiprocessor scheduling algorithm. Each motion state is regarded as a processor and each volume is regarded as a job. An efficient scheduling that completes all jobs in minimal time is maintained even when the motion pattern changes. Initial experiments demonstrated that SMV significantly increased the scan efficiency of navigatorgated MRI.}, author = {Vladimir Kolmogorov and Nguyen, Thành D and Nuval, Anthony and Spincemaille, Pascal and Prince, Martin R and Zabih, Ramin and Wang, Yusu}, journal = {Magnetic Resonance in Medicine}, number = {2}, pages = {362 -- 367}, publisher = {Wiley-Blackwell}, title = {{Multiprocessor scheduling implementation of the simultaneous multiple volume SMV navigator method}}, doi = {10.1002/mrm.20162}, volume = {52}, year = {2004}, } @article{3173, abstract = {In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available.}, author = {Vladimir Kolmogorov and Zabih, Ramin}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {2}, pages = {147 -- 159}, publisher = {IEEE}, title = {{What energy functions can be minimized via graph cuts? }}, doi = {10.1109/TPAMI.2004.1262177}, volume = {26}, year = {2004}, } @inproceedings{3177, abstract = {Feature space clustering is a popular approach to image segmentation, in which a feature vector of local properties (such as intensity, texture or motion) is computed at each pixel. The feature space is then clustered, and each pixel is labeled with the cluster that contains its feature vector. A major limitation of this approach is that feature space clusters generally lack spatial coherence (i.e., they do not correspond to a compact grouping of pixels). In this paper, we propose a segmentation algorithm that operates simultaneously in feature space and in image space. We define an energy function over both a set of clusters and a labeling of pixels with clusters. In our framework, a pixel is labeled with a single cluster (rather than, for example, a distribution over clusters). Our energy function penalizes clusters that are a poor fit to the data in feature space, and also penalizes clusters whose pixels lack spatial coherence. The energy function can be efficiently minimized using graph cuts. Our algorithm can incorporate both parametric and non-parametric clustering methods. It can be applied to many optimization-based clustering methods, including k-means and k-medians, and can handle models which are very close in feature space. Preliminary results are presented on segmenting real and synthetic images, using both parametric and non-parametric clustering.}, author = {Zabih, Ramin and Vladimir Kolmogorov}, pages = {437 -- 444}, publisher = {IEEE}, title = {{Spatially coherent clustering using graph cuts}}, doi = {10.1109/CVPR.2004.1315196}, volume = {2}, year = {2004}, } @article{3178, abstract = {Minimum cut/maximum flow algorithms on graphs have emerged as an increasingly useful tool for exactor approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut/max flow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push -relabel" methods and algorithms based on Ford-Fulkerson style "augmenting paths." We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementation of our max-flow/min-cut algorithm is available upon request for research purposes.}, author = {Boykov, Yuri and Vladimir Kolmogorov}, journal = {IEEE Transactions on Pattern Analysis and Machine Intelligence}, number = {9}, pages = {1124 -- 1137}, publisher = {IEEE}, title = {{An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision}}, doi = {10.1109/TPAMI.2004.60}, volume = {26}, year = {2004}, } @inproceedings{3179, abstract = {The problem of efficient, interactive foreground/background segmentation in still images is of great practical importance in image editing. Classical image segmentation tools use either texture (colour) information, e.g. Magic Wand, or edge (contrast) information, e.g. Intelligent Scissors. Recently, an approach based on optimization by graph-cut has been developed which successfully combines both types of information. In this paper we extend the graph-cut approach in three respects. First, we have developed a more powerful, iterative version of the optimisation. Secondly, the power of the iterative algorithm is used to simplify substantially the user interaction needed for a given quality of result. Thirdly, a robust algorithm for "border matting" has been developed to estimate simultaneously the alpha-matte around an object boundary and the colours of foreground pixels. We show that for moderately difficult examples the proposed method outperforms competitive tools.}, author = {Rother, Carsten and Vladimir Kolmogorov and Blake, Andrew}, number = {3}, pages = {309 -- 314}, publisher = {ACM}, title = {{"GrabCut" - Interactive foreground extraction using iterated graph cuts }}, doi = {10.1145/1015706.1015720}, volume = {23}, year = {2004}, } @inproceedings{3208, abstract = {A new technique for proving the adaptive indistinguishability of two systems, each composed of some component systems, is presented, using only the fact that corresponding component systems are non-adaptively indistinguishable. The main tool is the definition of a special monotone condition for a random system F, relative to another random system G, whose probability of occurring for a given distinguisher D is closely related to the distinguishing advantage ε of D for F and G, namely it is lower and upper bounded by ε and (1+ln1), respectively. A concrete instantiation of this result shows that the cascade of two random permutations (with the second one inverted) is indistinguishable from a uniform random permutation by adaptive distinguishers which may query the system from both sides, assuming the components’ security only against non-adaptive one-sided distinguishers. As applications we provide some results in various fields as almost k-wise independent probability spaces, decorrelation theory and computational indistinguishability (i.e., pseudo-randomness).}, author = {Maurer, Ueli M and Krzysztof Pietrzak}, pages = {410 -- 427}, publisher = {Springer}, title = {{Composition of random systems: When two weak make one strong}}, doi = {10.1007/978-3-540-24638-1_23}, volume = {2951}, year = {2004}, } @article{11762, abstract = {In this paper, we describe six algorithmic problems that arise in web search engines and that are not or only partially solved: (1) Uniformly sampling of web pages; (2) modeling the web graph; (3) finding duplicate hosts; (4) finding top gainers and losers in data streams; (5) finding large dense bipartite graphs; and (6) understanding how eigenvectors partition the web.}, author = {Henzinger, Monika H}, issn = {1944-9488}, journal = {Internet Mathematics}, number = {1}, pages = {115--123}, publisher = {Internet Mathematics}, title = {{Algorithmic challenges in web search engines}}, doi = {10.1080/15427951.2004.10129079}, volume = {1}, year = {2004}, } @article{8517, abstract = {We consider the evolution of a connected set on the plane carried by a space periodic incompressible stochastic flow. While for almost every realization of the stochastic flow at time t most of the particles are at a distance of order equation image away from the origin, there is a measure zero set of points that escape to infinity at the linear rate. We study the set of points visited by the original set by time t and show that such a set, when scaled down by the factor of t, has a limiting nonrandom shape.}, author = {Dolgopyat, Dmitry and Kaloshin, Vadim and Koralov, Leonid}, issn = {0010-3640}, journal = {Communications on Pure and Applied Mathematics}, keywords = {Applied Mathematics, General Mathematics}, number = {9}, pages = {1127--1158}, publisher = {Wiley}, title = {{A limit shape theorem for periodic stochastic dispersion}}, doi = {10.1002/cpa.20032}, volume = {57}, year = {2004}, } @article{8518, author = {Koralov, Leonid and Kaloshin, Vadim and Dolgopyat, Dmitry}, issn = {0091-1798}, journal = {The Annals of Probability}, number = {1A}, pages = {1--27}, publisher = {Institute of Mathematical Statistics}, title = {{Sample path properties of the stochastic flows}}, doi = {10.1214/aop/1078415827}, volume = {32}, year = {2004}, } @article{864, abstract = {We present a method for prediction of functional sites in a set of aligned protein sequences. The method selects sites which are both well conserved and clustered together in space, as inferred from the 3D structures of proteins included in the alignment. We tested the method using 86 alignments from the NCBI CDD database, where the sites of experimentally determined ligand and/or macromolecular interactions are annotated. In agreement with earlier investigations, we found that functional site predictions are most successful when overall background sequence conservation is low, such that sites under evolutionary constraint become apparent. In addition, we found that averaging of conservation values across spatially clustered sites improves predictions under certain conditions: that is, when overall conservation is relatively high and when the site in question involves a large macromolecular binding interface. Under these conditions it is better to look for clusters of conserved sites than to look for particular conserved sites.}, author = {Panchenko, Anna R and Fyodor Kondrashov and Bryant, Stephen H}, journal = {Protein Science}, number = {4}, pages = {884 -- 892}, publisher = {Wiley-Blackwell}, title = {{Prediction of functional sites by analysis of sequence and structure conservation}}, doi = {10.1110/ps.03465504}, volume = {13}, year = {2004}, } @article{870, abstract = {Only a fraction of eukaryotic genes affect the phenotype drastically. We compared 18 parameters in 1273 human morbid genes, known to cause diseases, and in the remaining 16 580 unambiguous human genes. Morbid genes evolve more slowly, have wider phylogenetic distributions, are more similar to essential genes of Drosophila melanogaster, code for longer proteins containing more alanine and glycine and less histidine, lysine and methionine, possess larger numbers of longer introns with more accurate splicing signals and have higher and broader expressions. These differences make it possible to classify as non-morbid 34% of human genes with unknown morbidity, when only 5% of known morbid genes are incorrectly classified as non-morbid. This classification can help to identify disease-causing genes among multiple candidates.}, author = {Fyodor Kondrashov and Ogurtsov, Aleksey Yu and Kondrashov, Alexey S}, journal = {Nucleic Acids Research}, number = {5}, pages = {1731 -- 1737}, publisher = {Oxford University Press}, title = {{Bioinformatical assay of human gene morbidity}}, doi = {10.1093/nar/gkh330}, volume = {32}, year = {2004}, } @article{875, abstract = {The dominance of wild-type alleles and the concomitant recessivity of deleterious mutant alleles might have evolved by natural selection or could be a by-product of the molecular and physiological mechanisms of gene action. We compared the properties of human haplosufficient genes, whose wild-type alleles are dominant over loss-of-function alleles, with haploinsufficient (recessive wild-type) genes, which produce an abnormal phenotype when heterozygous for a loss-of-function allele. The fraction of haplosufficient genes is the highest among the genes that encode enzymes, which is best compatible with the physiological theory. Haploinsufficient genes, on average, have more paralogs than haplosufficient genes, supporting the idea that gene dosage could be important for the initial fixation of duplications. Thus, haplo(in)sufficiency of a gene and its propensity for duplication might have a common evolutionary basis.}, author = {Fyodor Kondrashov and Koonin, Eugene V}, journal = {Trends in Genetics}, number = {7}, pages = {287 -- 291}, publisher = {Elsevier}, title = {{A common framework for understanding the origin of genetic dominance and evolutionary fates of gene duplications}}, doi = {10.1016/j.tig.2004.05.001}, volume = {20}, year = {2004}, } @article{889, abstract = {The function of protein and RNA molecules depends on complex epistatic interactions between sites. Therefore, the deleterious effect of a mutation can be suppressed by a compensatory second-site substitution. In relating a list of 86 pathogenic mutations in human IRNAs encoded by mitochondrial genes to the sequences of their mammalian orthologs, we noted that 52 pathogenic mutations were present in normal tRNAs of one or several nonhuman mammals. We found at least five mechanisms of compensation for 32 pathogenic mutations that destroyed a Watson-Crick pair in one of the four tRNA stems: restoration of the affected Watson-Crick interaction (25 cases), strengthening of another pair (4 cases), creation of a new pair (8 cases), changes of multiple interactions in the affected stem (11 cases) and changes involving the interaction between the loop and stem structures (3 cases). A pathogenic mutation and its compensating substitution are fixed in a lineage in rapid succession, and often a compensatory interaction evolves convergently in different clades. At least 10%, and perhaps as many as 50%, of all nucleotide substitutions in evolving mammalian (RNAs participate in such interactions, indicating that the evolution of tRNAs proceeds along highly epistatic fitness ridges.}, author = {Kern, Andrew D and Fyodor Kondrashov}, journal = {Nature Genetics}, number = {11}, pages = {1207 -- 1212}, publisher = {Nature Publishing Group}, title = {{Mechanisms and convergence of compensatory evolution in mammalian mitochondrial tRNAs}}, doi = {10.1038/ng1451}, volume = {36}, year = {2004}, } @article{898, abstract = {New alleles become fixed owing to random drift of nearly neutral mutations or to positive selection of substantially advantageous mutations. After decades of debate, the fraction of fixations driven by selection remains uncertain. Within 9,390 genes, we analysed 28,196 codons at which rat and mouse differ from each other at two nucleotide sites and 1,982 codons with three differences. At codons where rat-mouse divergence involved two non-synonymous substitutions, both of them occurred in the same lineage, either rat or mouse, in 64% of cases; however, independent substitutions would occur in the same lineage with a probability of only 50%. All three non-synonymous substitutions occurred in the same lineage for 46% of codons, instead of the 25% expected. Furthermore, comparison of 12 pairs of prokaryotic genomes also shows clumping of multiple non-synonymous substitutions in the same lineage. This pattern cannot be explained by correlated mutation or episodes of relaxed negative selection, but instead indicates that positive selection acts at many sites of rapid, successive amino acid replacement.}, author = {Bazykin, Georgii A and Fyodor Kondrashov and Ogurtsov, Aleksey Yu and Sunyaev, Shamil R and Kondrashov, Alexey S}, journal = {Nature}, number = {6991}, pages = {558 -- 562}, publisher = {Nature Publishing Group}, title = {{Positive selection at sites of multiple amino acid replacements since rat-mouse divergence}}, doi = {10.1038/nature02601}, volume = {429}, year = {2004}, } @article{1963, abstract = {The mechanism coupling electron transfer and proton pumping in respiratory complex I (NADH-ubiquinone oxidoreductase) has not been established, but it has been suggested that it involves conformational changes. Here, the influence of substrates on the conformation of purified complex I from Escherichia coli was studied by cross-linking and electron microscopy. When a zero-length cross-linking reagent was used, the presence of NAD(P)H, in contrast to that of NAD+, prevented the formation of cross-links between the hydrophilic subunits of the complex, including NuoB, NuoI, and NuoCD. Comparisons using different cross-linkers suggested that NuoB, which is likely to coordinate the key iron-sulfur cluster N2, is the most mobile subunit. The presence of NAD(P)H led also to enhanced proteolysis of subunit NuoG. These data indicate that upon NAD(P)H binding, the peripheral arm of the complex adopts a more open conformation, with increased distances between subunits. Single particle analysis showed the nature of this conformational change. The enzyme retains its L-shape in the presence of NADH, but exhibits a significantly more open or expanded structure both in the peripheral arm and, unexpectedly, in the membrane domain also.}, author = {Mamedova, Aygun A and Holt, Peter J and Carroll, Joe D and Leonid Sazanov}, journal = {Journal of Biological Chemistry}, number = {22}, pages = {23830 -- 23836}, publisher = {American Society for Biochemistry and Molecular Biology}, title = {{Substrate-induced conformational change in bacterial complex I}}, doi = {10.1074/jbc.M401539200}, volume = {279}, year = {2004}, } @article{209, author = {Timothy Browning and Heath-Brown, Roger}, journal = {Inventiones Mathematicae}, number = {3}, pages = {553 -- 573}, publisher = {Unknown}, title = {{Equal sums of three powers}}, doi = {10.1007/s00222-004-0360-9}, volume = {157}, year = {2004}, } @article{2308, abstract = {It is widely believed that the inflammatory events mediated by microglial activation contribute to several neurodegenerative processes. Alzheimer's disease, for example, is characterized by an accumulation of β-amyloid protein (Aβ) in neuritic plaques that are infiltrated by reactive microglia and astrocytes. Although Aβ and its fragment 25-35 exert a direct toxic effect on neurons, they also activate microglia. Microglial activation is accompanied by morphological changes, cell proliferation, and release of various cytokines and growth factors. A number of scientific reports suggest that the increased proliferation of microglial cells is dependent on ionic membrane currents and in particular on chloride conductances. An unusual chloride ion channel known to be associated with macrophage activation is the chloride intracellular channel-1 (CLIC1). Here we show that Aβ stimulation of neonatal rat microglia specifically leads to the increase in CLIC1 protein and to the functional expression of CLIC1 chloride conductance, both barely detectable on the plasma membrane of quiescent cells. CLIC1 protein expression in microglia increases after 24 hr of incubation with Aβ, simultaneously with the production of reactive nitrogen intermediates and of tumor necrosis factor-α (TNF-α). We demonstrate that reducing CLIC1 chloride conductance by a specific blocker [IAA-94 (R(+)-[(6,7-dichloro-2-cyclopentyl-2,3-dihydro-2-methyl-1-oxo-1H-inden-5yl)-oxy] acetic acid)] prevents neuronal apoptosis in neurons cocultured with Aβ-treated microglia. Furthermore, we show that small interfering RNAs used to knock down CLIC1 expression prevent TNF-α release induced by Aβ stimulation. These results provide a direct link between Aβ-induced microglial activation and CLIC1 functional expression.}, author = {Gaia Novarino and Fabrizi, Cinzia and Tonini, Raffaella and Denti, Michela A and Malchiodi, Albedi F and Lauro, Giuliana M and Sacchetti, Benedetto and Paradisi, Silvia and Ferroni, Arnaldo and Curmi, Paul M G and Breit, Samuel N and Mazzanti, Michele}, journal = {Journal of Neuroscience}, number = {23}, pages = {5322 -- 5330}, publisher = {Society for Neuroscience}, title = {{Involvement of the intracellular ion channel CLIC1 in microglia-mediated β-amyloid-induced neurotoxicity}}, doi = {10.1523/JNEUROSCI.1170-04.2004}, volume = {24}, year = {2004}, } @article{2355, abstract = {The BMV conjecture for traces, which states that Tr exp(A - λB) is the Laplace transform of a positive measure, is shown to be equivalent to two other statements: (i) The polynomial λ → Tr(A + λB) p has only non-negative coefficients for all A, B ≥ 0, p ∈ ℕ and (ii) λ → Tr(A + λB)-p is the Laplace transform of a positive measure for A, B ≥ 0, p > 0.}, author = {Lieb, Élliott H and Robert Seiringer}, journal = {Journal of Statistical Physics}, number = {1-2}, pages = {185 -- 190}, publisher = {Springer}, title = {{ Equivalent forms of the Bessis-Moussa-Villani conjecture}}, doi = {10.1023/B:JOSS.0000019811.15510.27}, volume = {115}, year = {2004}, } @article{2356, abstract = {Recent experimental and theoretical work has shown that there are conditions in which a trapped, low-density Bose gas behaves like the one-dimensional delta-function Bose gas solved years ago by Lieb and Liniger. This is an intrinsically quantum-mechanical phenomenon because it is not necessary to have a trap width that is the size of an atom - as might have been supposed - but it suffices merely to have a trap width such that the energy gap for motion in the transverse direction is large compared to the energy associated with the motion along the trap. Up to now the theoretical arguments have been based on variational - perturbative ideas or numerical investigations. In contrast, this paper gives a rigorous proof of the one-dimensional behavior as far as the ground state energy and particle density are concerned. There are four parameters involved: the particle number, N, transverse and longitudinal dimensions of the trap, r and L, and the scattering length a of the interaction potential. Our main result is that if r/L → 0 and N → ∞ the ground state energy and density can be obtained by minimizing a one-dimensional density functional involving the Lieb-Liniger energy density with coupling constant ∼ a/r 2. This density functional simplifies in various limiting cases and we identify five asymptotic parameter regions altogether. Three of these, corresponding to the weak coupling regime, can also be obtained as limits of a three-dimensional Gross-Pitaevskii theory. We also show that Bose-Einstein condensation in the ground state persists in a part of this regime. In the strong coupling regime the longitudinal motion of the particles is strongly correlated. The Gross-Pitaevskii description is not valid in this regime and new mathematical methods come into play.}, author = {Lieb, Élliott H and Robert Seiringer and Yngvason, Jakob}, journal = {Communications in Mathematical Physics}, number = {2}, pages = {347 -- 393}, publisher = {Springer}, title = {{One-dimensional behavior of dilute, trapped Bose gases}}, doi = {10.1007/s00220-003-0993-3}, volume = {244}, year = {2004}, }