960732
Computing the Assignment of Orthologous Genes via Genome Rearrangement
The assignment of orthologous genes between a pair of genomes is a fundamental and challenging problem in comparative genomics. Existing methods that assign orthologs based on the similarity between DNA or protein sequences may make erroneous assignments when sequence similarity does not clearly delineate the evolutionary relationship among genes of the same families. In this paper, we present a new approach to ortholog assignment that takes into account both sequence similarity and evolutionary events at genome level, where orthologous genes are assumed to correspond to each other in the most parsimonious evolving scenario under genome rearrangement. It is then formulated as a problem of computing the signed reversal distance with duplicates between two genomes of interest, for which an efcient heuristic algorithm was given by introducing two new optimization problems, minimum common partition and maximum cycle decomposition. Following this approach, we have implemented a high-throughput system for assigning orthologs on a genome scale, called SOAR, and tested it on both simulated data and real genome sequence data. Compared to a recent ortholog assignment method based entirely on homology search (called INPARANOID), SOAR shows a marginally better performance in terms of sensitivity on the real data set because it was able to identify several correct orthologous pairs that were missed by INPARANOID. The simulation results demonstrate that SOAR in general performs better than the iterated exemplar algorithm in terms of computing the reversal distance and assigning correct orthologs.
1529480
A compression algorithm for DNA sequences and its applications in genome comparison
We present a lossless compression algorithm, <italic>Gen-Compress</italic>, for DNA sequences, based on searching for approximate repeats. Our algorithm achieves the best compression ratios for benchmark DNA sequences, comparing to other DNA compression programs [3, 7]. Significantly better compression results show that the approximate repeats are one of the main hidden regularities in DNA sequences.
We then describe a theory of measuring the relatedness between two DNA sequences. We propose to use <italic>d</italic>(<italic>x</italic>, <italic>y</italic>) = 1 — <italic>K</italic>(<italic>x</italic>) - <italic>K</italic>(<italic>x</italic>|<italic>y</italic>)/<italic>K</italic>(<italic>xy</italic> to measure the distance of any two sequences, where <italic>K</italic>  stands for Kolmogorov complexity [5]. Here, <italic>K</italic>(<italic>x</italic>) - <italic>K</italic>(<italic>x</italic>|<italic>y</italic>) is the mutual information shared by <italic>x</italic> and <italic>y</italic>. But mutual information is not a distance, there is no triangle inequality. The distance <italic>d</italic>(<italic>x</italic>, <italic>y</italic>) is symmetric. It also satisfies the triangle inequality, and furthermore, it is universal [4].
It has not escaped our notice that the distance measure we have postulated can be immediately used to construct evolutionary trees from DNA sequences, especially those that cannot be aligned, such as complete genomes. With more and more genomes sequenced, constructing trees from genomes becomes possible [1, 2, 6, 8].  Kolmogorov complexity is not computable. We use <italic>GenCompress</italic> to approximate it. We present strong experimental support for this theory, and demonstrate its applicability by correctly constructing a 16S (18S) rRNA tree, and a whole genome tree for several species of bacteria. Larger scale experiments are underway at the University of Waterloo, with very promising results.
30296056
Computational inference of regulatory pathways in microbes
We present a computational protocol for inference of regulatory and signaling pathways in a microbial cell, through mining "high-throughput" biological data of various types, literature search, and computer-assisted human inference. This protocol consists of four key components: (a) construction of template pathways for microbial genomes related to the target genome, which have either been thoroughly studied or had a significant amount of relevant experimental data, (b) inference of target pathways for the target genome, by combining the template pathway models and target genome-specific information, (c) assignment of genes of the target genome to each individual functional roles in the pathway model, and (d) validation and refinement of the pathway models using pathway-specific experimental data or other information. To demonstrate the effectiveness of this procedure, we have applied this computational protocol to the construction of the phosphorus assimilation pathways in synechococcus WH8102. In this paper, we present a model of the core component of this pathway and provide our justification in support of the predicted model.
12811258
A Parsimony Approach to Genome-Wide Ortholog Assignment
The assignment of orthologous genes between a pair of genomes is a fundamental and challenging problem in comparative genomics, since many computational methods for solving various biological problems critically rely on bona fide orthologs as input. While it is usually done using sequence similarity search, we recently proposed a new combinatorial approach that combines sequence similarity and genome rearrangement. This paper continues the development of the approach and unites genome rearrangement events and (post-speciation) duplication events in a single framework under the parsimony principle. In this framework, orthologous genes are assumed to correspond to each other in the most parsimonious evolutionary scenario involving both genome rearrangement and (post-speciation) gene duplication. Besides several original algorithmic contributions, the enhanced method allows for the detection of inparalogs. Following this approach, we have implemented a high-throughput system for ortholog assignment on a genome scale, called MSOAR, and applied it to the genomes of human and mouse. As the result will show, MSOAR is able to find 99 more true orthologs than the INPARANOID program did. We have also compared MSOAR with the iterated exemplar algorithm on simulated data and found that MSOAR performed very well in terms of assignment accuracy. These test results indiate that our approach is very promising for genome-wide ortholog assignment.
8099146
A new compression scheme for color-quantized images
An efficient compression scheme for color-quantized images based on progressive coding of color information has been developed. Instead of sorting color indexes into a linear list struc- ture, a binary-tree structure of color indexes is proposed. With this structure, the new algorithm can progressively recover an image from two colors to all of the colors contained in the original image, i.e., a lossless recovery is achieved. Experimental results showed that it can efficiently compress images in both lossy and lossless cases. Typically for color-quantized Lena image with 256 colors, the algorithm achieved 0.5 bpp below state-of-the-art lossless com- pression methods while preserving the efficient lossy compression. Such a compression scheme is very attractive to many applications that require the ability of fast browsing or progressive transmis- sion, and if necessary, to exactly recover the original image. Index Terms—Color-quantized images, data compression, index sorting, progressive refinement.
1552680
Shared information and program plagiarism detection
A fundamental question in information theory and in computer science is how to measure similarity or the amount of shared information between two sequences. We have proposed a metric, based on Kolmogorov complexity, to answer this question and have proven it to be universal. We apply this metric in measuring the amount of shared information between two computer programs, to enable plagiarism detection. We have designed and implemented a practical system SID (Software Integrity Diagnosis system) that approximates this metric by a heuristic compression algorithm. Experimental results demonstrate that SID has clear advantages over other plagiarism detection systems. SID system server is online at http://software.bioinformatics.uwaterloo.ca/SID/.
14274462
Region-Based Image Clustering and Retrieval Using Multiple Instance Learning
Multiple Instance Learning (MIL) is a special kind of supervised learning problem that has been studied actively in recent years. We propose an approach based on One-Class Support Vector Machine (SVM) to solve MIL problem in the region-based Content Based Image Retrieval (CBIR). This is an area where a huge number of image regions are involved. For the sake of efficiency, we adopt a Genetic Algorithm based clustering method to reduce the search space. Relevance Feedback technique is incorporated to provide progressive guidance to the learning process. Performance is evaluated and the effectiveness of our retrieval algorithm is demonstrated in comparative studies.
14272026
Fully automated facial symmetry axis detection in frontal color images
We consider the problem of automatically detecting a facial symmetry axis in what we will call a standard human face image (acquired when the subject is looking directly into the camera, in front of a clean gray background under controlled illumination). Images of this kind are encountered in face recognition scenarios; this detection should facilitate more sophisticated facial image processing. The proposed method is based on GLDH (gray level difference histogram) analysis and consists of three components: (1) the face region detection stage crops an approximate face region out of the background, (2) symmetry detection discovers a vertical axis to optimally bisect the region of interest, assuming it is bilaterally symmetric, and (3) orientation adjustment aligns the angle of the symmetry axis with the orientation of the face. An implementation of the method is described, and results are presented. This detector's robust performance is evidenced by its success finding symmetry axes in more than 7,500 images collected from 600 distinct subjects. One of our method's most noteworthy contributions is that, according to our experimental results, many of the automatically detected axes are more accurate than the reference axes. Our automated detector is a powerful tool because it is not as susceptible to human error as its manual counterpart and, as the first application of its kind, it could potentially serve as a new biometric.
3822993
Learning by Examples: Identifying Key Concepts from Text Using Pre-Defined Inputs
1385145
Simulation based deadlock analysis for system level designs
In the design of highly complex, heterogeneous, and concurrent systems, deadlock detection and resolution remains an important issue. In this paper, we systematically analyze the synchronization dependencies in concurrent systems modeled in the Metropolis design environment, where system functions, high level architectures and function-architecture mappings can be modeled and simulated. We propose a data structure called the dynamic synchronization dependency graph, which captures the runtime (blocking) dependencies. A loop-detection algorithm is then used to detect deadlocks and help designers quickly isolate and identify modeling errors that cause the deadlock problems. We demonstrate our approach through a real world design example, which is a complex functional model for video processing and a high level model of function-architecture mapping.
694287
Automatic trace analysis for logic of constraints
Verification of system designs continues to be a major challenge today. Simulation remains the primary tool for making sure that implementations perform as they should. We present algorithms to automatically generate trace checkers from formulas written in the formal quantitative constraint language, Logic Of Constraints (LOC), to analyze the simulation traces for functional and performance constraint violations. For many interesting formulas, the checkers exhibit linear time complexity and constant memory usage. We illustrate the usefulness and efficiency of this approach with large designs and traces.