16937671
A Fast Algorithm for Approximate String Matching on Gene Sequences
Approximate string matching is a fundamental and challenging problem in computer science, for which a fast algorithm is highly demanded in many applications including text processing and DNA sequence analysis. In this paper, we present a fast algorithm for approximate string matching, called FAAST. It aims at solving a popular variant of the approximate string matching problem, the k-mismatch problem, whose objective is to find all occurrences of a short pattern in a long text string with at most k mismatches. FAAST generalizes the well-known Tarhio-Ukkonen algorithm by requiring two or more matches when calculating shift distances, which makes the approximate string matching process significantly faster than the Tarhio-Ukkonen algorithm. Theoretically, we prove that FAAST on average skips more characters than the Tarhio-Ukkonen algorithm in a single shift, and makes fewer character comparisons in an entire matching process. Experiments on both simulated data sets and real gene sequences also demonstrate that FAAST runs several times faster than the Tarhio-Ukkonen algorithm in all the cases that we tested.
12010325
An information-based sequence distance and its application to whole mitochondrial genome phylogeny
MOTIVATION
Traditional sequence distances require an alignment and therefore are not directly applicable to the problem of whole genome phylogeny where events such as rearrangements make full length alignments impossible. We present a sequence distance that works on unaligned sequences using the information theoretical concept of Kolmogorov complexity and a program to estimate this distance.


RESULTS
We establish the mathematical foundations of our distance and illustrate its use by constructing a phylogeny of the Eutherian orders using complete unaligned mitochondrial genomes. This phylogeny is consistent with the commonly accepted one for the Eutherians. A second, larger mammalian dataset is also analyzed, yielding a phylogeny generally consistent with the commonly accepted one for the mammals.


AVAILABILITY
The program to estimate our sequence distance, is available at http://www.cs.cityu.edu.hk/~cssamk/gencomp/GenCompress1.htm. The distance matrices used to generate our phylogenies are available at http://www.math.uwaterloo.ca/~mli/distance.html.
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.
12408696
DNACompress: fast and effective DNA sequence compression
While achieving the best compression ratios for DNA sequences, our new DNACompress program significantly improves the running time of all previous DNA compression programs.
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.
28317923
Characterization of graphs with equal domination and connected domination numbers
Arumugam and Paulraj Joseph (Discrete Math 206 (1999) 45) have characterized trees, unicyclic graphs and cubic graphs with equal domination and connected domination numbers. In this paper, we extend their results and characterize the class of block graphs and cactus graphs for which the domination number is equal to the connected domination number.
8954904
Modification of the AdaBoost-based Detector for Partially Occluded Faces
While face detection seems a solved problem under general conditions, most state-of-the-art systems degrade rapidly when faces are partially occluded by other objects. This paper presents a solution to detect partially occluded faces by reasonably modifying the AdaBoost-based face detector. Our basic idea is that the weak classifiers in the AdaBoost-based face detector, each corresponding to a Haar-like feature, are inherently a patch-based model. Therefore, one can divide the whole face region into multiple patches, and map those weak classifiers to the patches. The weak classifiers belonging to each patch are re-formed to be a new classifier to determine if it is a valid face patch - without occlusion. Finally, we combine all of the valid face patches by assigning the patches with different weights to make the final decision whether the input subwindow is a face. The experimental results show that the proposed method is promising for the detection of occluded faces
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.
2587881
Isomap Based on the Image Euclidean Distance
Scientists find that the human perception is based on the similarity on the manifold of data set. Isometric feature mapping (isomap) is one of the representative techniques of manifold. It is intuitive, well understood and produces reasonable mapping results. However, if the input data for manifold learning are corrupted with noises, the isomap algorithm is topologically unstable. In this paper, we present an improved manifold learning method when the input data are images - the image Euclidean distance based isomap (imisomap), in which we use a new distance for images called image Euclidean distance (IMED). Experimental results demonstrate a consistent performance improvement of the algorithm imisomap over the traditional isomap based on Euclidean distance
5884737
Logic of constraints: a quantitative performance and functional constraint formalism
In the era of billion-transistor design, it is critical to establish effective verification methodologies from the system level, all the way down to the implementations. In this paper, we introduce logic of constraints (LOC), a logic that is particularly suited to express quantitative performance constraints as well as functional constraints. We analyze the expressiveness of LOC and show that it is important and different from linear temporal logic, upon which traditional hardware assertion languages (e.g., PSL and OpenVera) are based. We propose an automatic simulation trace checking/runtime monitoring methodology that can be used to verify system designs very efficiently. Since a subset of LOC is decidable, we also discuss the formal verification approach for LOC formulas. Through several industrial case studies, we demonstrate the usefulness of the LOC formalism and the corresponding simulation and verification approach at the higher transaction level of abstraction.