@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{902,
abstract = {We compare the functional spectrum of protein evolution in two separate animal lineages with respect to two hypotheses: (1) rates of divergence are distributed similarly among functional classes within both lineages, indicating that selective pressure on the proteome is largely independent of organismic-level biological requirements; and (2) rates of divergence are distributed differently among functional classes within each lineage, indicating species-specific selective regimes impact genome-wide substitutional patterns. Integrating comparative genome sequence with data from tissue-specific expressed-sequence-tag (EST) libraries and detailed database annotations, we find a functional genomic signature of rapid evolution and selective constraint shared between mammalian and nematode lineages despite their extensive morphological and ecological differences and distant common ancestry. In both phyla, we find evidence of accelerated evolution among components of molecular systems involved in coevolutionary change. In mammals, lineage-specific fast evolving genes include those involved in reproduction, immunity, and possibly, maternal-fetal conflict. Likelihood ratio tests provide evidence for positive selection in these rapidly evolving functional categories in mammals. In contrast, slowly evolving genes, in terms of amino acid or insertion/deletion (indel) change, in both phyla are involved in core molecular processes such as transcription, translation, and protein transport. Thus, strong purifying selection appears to act on the same core cellular processes in both mammalian and nematode lineages, whereas positive and/or relaxed selection acts on different biological processes in each lineage.},
author = {Castillo-Davis, Cristian I and Fyodor Kondrashov and Hartl, Daniel L and Kulathinal, Rob J},
journal = {Genome Research},
number = {5},
pages = {802 -- 811},
publisher = {Cold Spring Harbor Laboratory Press},
title = {{The functional genomic distribution of protein divergence in two animal phyla: Coevolution, genomic conflict, and constraint}},
doi = {10.1101/gr.2195604},
volume = {14},
year = {2004},
}
@article{1456,
abstract = {We study the space of L2 harmonic forms on complete manifolds with metrics of fibred boundary or fibred cusp type. These metrics generalize the geometric structures at infinity of several different well-known classes of metrics, including asymptotically locally Euclidean manifolds, the (known types of) gravitational instantons, and also Poincaré metrics on ℚ-rank 1 ends of locally symmetric spaces and on the complements of smooth divisors in Kähler manifolds. The answer in all cases is given in terms of intersection cohomology of a stratified compactification of the manifold. The L2 signature formula implied by our result is closely related to the one proved by Dai and more generally by Vaillant and identifies Dai's τ-invariant directly in terms of intersection cohomology of differing perversities. This work is also closely related to a recent paper of Carron and the forthcoming paper of Cheeger and Dai. We apply our results to a number of examples, gravitational instantons among them, arising in predictions about L2 harmonic forms in duality theories in string theory.},
author = {Tamas Hausel and Hunsicker, Eugénie and Mazzeo, Rafe R},
journal = {Duke Mathematical Journal},
number = {3},
pages = {485 -- 548},
publisher = {Duke University Press},
title = {{Hodge cohomology of gravitational instantons}},
doi = {10.1215/S0012-7094-04-12233-X},
volume = {122},
year = {2004},
}
@article{1464,
abstract = {The moduli space of stable vector bundles on a Riemann surface is smooth when the rank and degree are coprime, and is diffeomorphic to the space of unitary connections of central constant curvature. A classic result of Newstead and Atiyah and Bott asserts that its rational cohomology ring is generated by the universal classes, that is, by the Kunneth components of the Chern classes of the universal bundle.
This paper studies the larger, non-compact moduli space of Higgs bundles, as introduced by Hitchin and Simpson, with values in the canonical bundle K. This is diffeomorphic to the space of all connections of central constant curvature, whether unitary or not. The main result of the paper is that, in the rank 2 case, the rational cohomology ring of this space is again generated by universal classes.
The spaces of Higgs bundles with values in K(n) for n > 0 turn out to be essential to the story. Indeed, we show that their direct limit has the homotopy type of the classifying space of the gauge group, and hence has cohomology generated by universal classes. 2000 Mathematics Subject Classification 14H60 (primary), 14D20, 14H81, 32Q55, 58D27 (secondary). },
author = {Tamas Hausel and Thaddeus, Michael},
journal = {Proceedings of the London Mathematical Society},
number = {3},
pages = {632 -- 658},
publisher = {Oxford University Press},
title = {{Generators for the cohomology ring of the moduli space of rank 2 higgs bundles}},
doi = {10.1112/S0024611503014618},
volume = {88},
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},
}