38762001
Pattern Matching for Arc-Annotated Sequences
A study of pattern matching for arc-annotated sequences is started. An O(nm) time algorithm is given to determine whether a length m sequence with nested arc annotations is an arc-preserving subsequence of a length n sequence with nested arc annotations, called APS(NESTED,NESTED). Arc-annotated sequences and, in particular, those with nested arc structure are motivated by applications in RNA structure comparison. Our algorithm can be used to accelerate a recent fixed-parameter algorithm for LAPCS(NESTED,NESTED) and generalizes results for ordered tree inclusion problems. In particular, the presented dynamic programming methodology implies a quadratic time algorithm for an open problem posed by Vialette.
9767043
The Computational Complexity of Avoiding Forbidden Submatrices by Row Deletions
We initiate a systematic study of the ROW DELETION(B) problem on matrices: Given an input matrix A and a fixed "forbidden submatrix" B, the task is to remove a minimum number of rows from A such that no row or column permutation of B occurs as a submatrix in the resulting matrix. An application of this problem can be found, for instance, in the construction of perfect phylogenies. Establishing a strong connection to variants of the NP-complete HITTING SET problem, we describe and analyze structural properties of B that make ROW DELETION(B)NP-complete. On the positive side, the close relation with HITTING SET problems yields constant-factor polynomial-time approximation algorithms and fixed-parameter tractability results.
6020472
Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(c^[email protected]?m) time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in O(d^[email protected]?m) time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime O(2^[email protected]?m^2) for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite.
14425036
Parameterized Intractability of Distinguishing Substring Selection
Abstract
A central question in computational biology is the design of genetic
markers to distinguish between two given sets of (DNA) sequences. This question is formalized as 
the NP-complete Distinguishing Substring Selection problem (DSSS for short) which asks, given a set of "good" strings and a set of "bad" strings, for a solution string which is, with respect to the Hamming metric, "away" from the good strings and "close" to the bad strings. More precisely, given integers dg, db, and L, we ask for a length-L string s such that s has Hamming distance at least dg to every length-L substring of the good strings and such that every bad string has a length-L substring with Hamming distance at most db to s. Studying the parameterized complexity of DSSS, we show that, already for binary alphabet, DSSS is W[1]-hard with respect to its natural parameters. This, in particular, implies that a recently given polynomial-time approximation scheme (PTAS) by Deng et al. cannot be replaced by a so-called efficient polynomial-time approximation scheme (EPTAS) unless an unlikely collapse in parameterized complexity theory occurs. This is seemingly the first computational biology problem for which such a border between PTAS (which exists) and EPTAS (which is unlikely to exist) could be established. By way of contrast, for a special case of DSSS, we present an exact fixed-parameter algorithm solving the problem efficiently. In this way we also exhibit a sharp border between fixed-parameter tractability and intractability results.

1715544
Pattern matching for arc-annotated sequences
We study pattern matching for arc-annotated sequences. An O(nm) time algorithm is given for the problem to determine whether a length m sequence with nested arc annotation is an arc-preserving subsequence (aps) of a length n sequence with nested arc annotation, called APS(NESTED,NESTED). Arc-annotated sequences and, in particular, those with nested arc annotation are motivated by applications in RNA structure comparison. Our algorithm generalizes results for ordered tree inclusion problems and it is useful for recent fixed-parameter algorithms for LAPCS(NESTED,NESTED), which is the problem of computing a longest arc-preserving common subsequence of two sequences with nested arc annotations. In particular, the presented dynamic programming methodology implies a quadratic-time algorithm for an open problem posed by Vialette.
14944633
On Exact and Approximation Algorithms for Distinguishing Substring Selection
The NP-complete Distinguishing Substring Selection problem (DSSS for short) asks, given a set of “good” strings and a set of “bad” strings, for a solution string which is, with respect to Hamming metric, “away” from the good strings and “close” to the bad strings.
17686470
Inter-enterprise business document exchange
Electronic business document interoperation is the cornerstone of business process integration. An essential issue for business document interoperation is to maintain semantic consistency of the exchanged business documents between any two autonomous business communities, where the document sender and receiver have no misunderstanding in using the exchanged documents. Existing approaches to resolving this issue either adopts document standards to map heterogeneous document elements or applies business ontologies to mediate inconsistent document elements. While these approaches are effective in certain degree, the issues of limited flexibility and evolvability in using standards and the lack of accuracy in using ontologies to mediate document elements must be explored and resolved. This paper proposes a Collaborative Document Exchange (CODEX) approach to resolving the issues. In this approach, structures and concepts of business document are separated and layered in CODEX framework. Structures provide the commonality of business documents through classified concept identifiers while concepts support particularity of business documents through collaboration.
14231112
A Transparent Collaborative Integration Approach for Ad Hoc Product Data
Product data integration is an essential issue for many e-commerce interoperable business systems. Core to this issue is how to maintain semantic consistency between heterogeneous product data that are semantically different in structure, concept and context. To resolve the issue, this paper proposes a transparent collaborative integration approach, which is built on a layered framework of messaging, structure, concept and collaboration. The key to this framework is three collaboration engines, which resolves semantic consistency issues between millions of contextual vocabularies of SMEs
6234679
A Model-based Approach to Hair Region Segmentation
Hair regions represent an important external feature in many tasks involving the processing of human faces. Currently, the task of locating the hair region in a facial image requires manual intervention. In this paper we examine the different aspects of the hair region segmentation problem and develop an automatic system for such a problem. The system incorporates the human knowledge on where the hair is usually located in a facial image. Segmentation is performed via the classification of image pixels and is based on both textural and geometrical features. Experiments have shown that the segmentation results are generally satisfactory and are at least comparable to the performance of manual extraction.
13379605
Protein Fold Recognition Through Application of Residual Dipolar Coupling Data
Residual dipolar coupling (RDC) represents one of the most exciting emerging NMR techniques for studying protein structures. However, solving a protein structure using RDC data alone is a highly challenging problem as it often requires that the starting structure model be close to the actual structure of a protein, for the structure calculation procedure to be effective. We report in this paper a computer program, RDC-PROSPECT, for identification of a structural homolog or analog of a target protein in PDB, which best matches the 15N-1H RDC data of the protein recorded in a single ordering medium. The identified structural homolog/analog can then be used as a starting model for RDC-based structure calculation. Since RDC-PROSPECT uses only RDC data and predicted secondary structure information, its performance is virtually independent of sequence similarity between a target protein and its structural homolog/analog, making it applicable to protein targets out of the scope of current protein threading techniques. We have tested RDC-PROSPECT on all 15N-1H RDC data (representing 33 proteins) available in the BMRB database and the literature. The program correctly identified the structural folds for approximately 80% of the target proteins, significantly better than previously reported results, and achieved an average alignment accuracy of 97.9% residues within 4-residue shift. Through a careful algorithmic design, RDC-PROSPECT is at least one order of magnitude faster than previously reported algorithms for principal alignment frame search, making our algorithm fast enough for large-scale applications.
41178770
On matching coefficients
Abstract Explicit formulae are derived for the first four coefficients of the matching polynomial of a graph in terms of properties of the graph. An explicit formula is also derived for the number of triangles in the complement of a graph in terms of the parameters of the graph. Also, some extremal properties of regular multipartite graphs are identified.