Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Computer Science and Engineering, Biology (5)
- Computer Science and Engineering (4)
- Genome (4)
- Genomics (4)
- Algorithms (1)
-
- Boundary detection (1)
- Combinatorial mathematics (1)
- Combinatorics (1)
- Computational molecular biology (1)
- Coprocessors (1)
- Evolution (1)
- Field programmable gate arrays (1)
- Gene order (1)
- Genes (1)
- Genomic rearrangements (1)
- Object-oriented programming (1)
- Optimisation (1)
- Software architecture (1)
- Statistical shape analysis (1)
- Web services (1)
Articles 1 - 9 of 9
Full-Text Articles in Engineering
Gene Order Phylogeny Of The Genus Prochlorococcus, Haiwei Luo, Jian Shi, William Arndt, Jijun Tang, Robert Friedman
Gene Order Phylogeny Of The Genus Prochlorococcus, Haiwei Luo, Jian Shi, William Arndt, Jijun Tang, Robert Friedman
Faculty Publications
Background
Using gene order as a phylogenetic character has the potential to resolve previously unresolved species relationships. This character was used to resolve the evolutionary history within the genus Prochlorococcus, a group of marine cyanobacteria.
Methodology/Principal Findings
Orthologous gene sets and their genomic positions were identified from 12 species of Prochlorococcus and 1 outgroup species of Synechococcus. From this data, inversion and breakpoint distance-based phylogenetic trees were computed by GRAPPA and FastME. Statistical support of the resulting topology was obtained by application of a 50% jackknife resampling technique. The result was consistent and congruent with nucleotide sequence-based and gene-content based …
A Special-Purpose Architecture For Solving The Breakpoint Median Problem, Jason D. Bakos, Panormitis E. Elenis
A Special-Purpose Architecture For Solving The Breakpoint Median Problem, Jason D. Bakos, Panormitis E. Elenis
Faculty Publications
In this paper, we describe the design for a co-processor for whole-genome phylogenetic reconstruction. Our current design performs a parallelized breakpoint median computation, which is an expensive component of the overall application. When implemented on a field-programmable gate array (FPGA), our hardware breakpoint median achieves a maximum speedup of 1005times over software. When the coprocessor is used to accelerate the entire reconstruction procedure, we achieve a maximum application speedup of 417times. The results in this paper suggest that FPGA-based acceleration is a promising approach for computationally expensive phylogenetic problems, in spite of the fact that the involved algorithms are based …
Improving Reversal Median Computation Using Commuting Reversals And Cycle Information, William Arndt, Jijun Tang
Improving Reversal Median Computation Using Commuting Reversals And Cycle Information, William Arndt, Jijun Tang
Faculty Publications
In the past decade, genome rearrangements have attracted increasing attention from both biologists and computer scientists as a new type of data for phylogenetic analysis. Methods for reconstructing phylogeny from genome rearrangements include distance-based methods, MCMC methods, and direct optimization methods. The latter, pioneered by Sankoff and extended with the software suites GRAPPA and MGR, is the most accurate approach, but is very limited due to the difficulty of its scoring procedure—it must solve multiple instances of the reversal median problem to compute the score of a given tree. The reversal median problem is known to be NP-hard and all …
Multi-Break Rearrangements And Breakpoint Re-Uses: From Circular To Linear Genomes, Max A. Alekseyev
Multi-Break Rearrangements And Breakpoint Re-Uses: From Circular To Linear Genomes, Max A. Alekseyev
Faculty Publications
Multi-break rearrangements break a genome into multiple fragments and further glue them together in a new order. While 2-break rearrangements represent standard reversals, fusions, fissions, and translocations, 3-break rearrangements represent a natural generalization of transpositions. Alekseyev and Pevzner (2007a, 2008a) studied multi-break rearrangements in circular genomes and further applied them to the analysis of chromosomal evolution in mammalian genomes. In this paper, we extend these results to the more difficult case of linear genomes. In particular, we give lower bounds for the rearrangement distance between linear genomes and for the breakpoint re-use rate as functions of the number and proportion …
Evaluating Shape Correspondence For Statistical Shape Analysis: A Benchmark Study, Brent C. Munsell, Pahal Dalal, Song Wang
Evaluating Shape Correspondence For Statistical Shape Analysis: A Benchmark Study, Brent C. Munsell, Pahal Dalal, Song Wang
Faculty Publications
This paper introduces a new benchmark study to evaluate the performance of landmark-based shape correspondence used for statistical shape analysis. Different from previous shape-correspondence evaluation methods, the proposed benchmark first generates a large set of synthetic shape instances by randomly sampling a given statistical shape model that defines a ground-truth shape space. We then run a test shape-correspondence algorithm on these synthetic shape instances to identify a set of corresponded landmarks. According to the identified corresponded landmarks, we construct a new statistical shape model, which defines a new shape space. We finally compare this new shape space against the ground-truth …
Phylogenetic Reconstruction From Transpositions, Feng Yue, Meng Zhang, Jijun Tang
Phylogenetic Reconstruction From Transpositions, Feng Yue, Meng Zhang, Jijun Tang
Faculty Publications
Background
Because of the advent of high-throughput sequencing and the consequent reduction in the cost of sequencing, many organisms have been completely sequenced and most of their genes identified. It thus has become possible to represent whole genomes as ordered lists of gene identifiers and to study the rearrangement of these entities through computational means. As a result, genome rearrangement data has attracted increasing attentions from both biologists and computer scientists as a new type of data for phylogenetic analysis. The main events of genome rearrangements include inversions, transpositions and transversions. To date, GRAPPA and MGR are the most accurate …
Gene Rearrangement Analysis And Ancestral Order Inference From Chloroplast Genomes With Inverted Repeat, Feng Yue, Liying Cui, Claude W. Depamphilis, Bernard M.E. Moret, Jijun Tang
Gene Rearrangement Analysis And Ancestral Order Inference From Chloroplast Genomes With Inverted Repeat, Feng Yue, Liying Cui, Claude W. Depamphilis, Bernard M.E. Moret, Jijun Tang
Faculty Publications
Background
Genome evolution is shaped not only by nucleotide substitutions, but also by structural changes including gene and genome duplications, insertions, deletions and gene order rearrangements. The most popular methods for reconstructing phylogeny from genome rearrangements include GRAPPA and MGR. However these methods are limited to cases where equal gene content or few deletions can be assumed. Since conserved duplicated regions are present in many chloroplast genomes, the inference of inverted repeats is needed in chloroplast phylogeny analysis and ancestral genome reconstruction.
Results
We extend GRAPPA and develop a new method GRAPPA-IR to handle chloroplast genomes. A test of GRAPPA-IR …
Globally Optimal Grouping For Symmetric Closed Boundaries By Combining Boundary And Region Information, Joachim S. Stahl, Song Wang
Globally Optimal Grouping For Symmetric Closed Boundaries By Combining Boundary And Region Information, Joachim S. Stahl, Song Wang
Faculty Publications
Many natural and man-made structures have a boundary that shows a certain level of bilateral symmetry, a property that plays an important role in both human and computer vision. In this paper, we present a new grouping method for detecting closed boundaries with symmetry. We first construct a new type of grouping token in the form of symmetric trapezoids by pairing line segments detected from the image. A closed boundary can then be achieved by connecting some trapezoids with a sequence of gap-filling quadrilaterals. For such a closed boundary, we define a unified grouping cost function in a ratio form: …
Web-Scale Workflow: Integrating Distributed Services, M. Brian Blake, Michael N. Huhns
Web-Scale Workflow: Integrating Distributed Services, M. Brian Blake, Michael N. Huhns
Faculty Publications
Modular applications, components, and services are all ways of describing the product of an organization's efforts to embody its capabilities in autonomous software modules. In fact, the integration of services using well-established workflow paradigms could amplify an organization's capabilities with the creation of a full-blown, inter-organizational system of systems. This is the essence of Web-scale workflows. Considering the recent popularity and acceptance of service-oriented technologies, the application of such distributed systems is only limited by imagination, but it's also important to understand existing research challenges and their implications to various Web-scale workflow domains.