Laxmi Parida

TCS Journal 2014 Journal Article

Irredundant tandem motifs

• Laxmi Parida
• Cinzia Pizzi
• Simona E. Rombo

Eliminating the possible redundancy from a set of candidate motifs occurring in an input string is fundamental in many applications. The existing techniques proposed to extract irredundant motifs are not suitable when the motifs to search for are structured, i. e. , they are made of two (or several) subwords that co-occur in a text string s of length n. The main effort of this work is studying and characterizing a compact class of tandem motifs, that is, pairs of substrings 〈 m 1, m 2 〉 occurring in tandem within a maximum distance of d symbols in s, where d is an integer constant given in input. To this aim, we first introduce the concept of maximality, related to four specific conditions that hold only for this class of motifs. Then, we eliminate the remaining redundancy by defining the notion of irredundancy for tandem motifs. We prove that the number of non-overlapping irredundant tandem motifs is O ( d 2 n ) which, considering d as a constant, leads to a linear number of tandems in the length of the input string. This is an order of magnitude less than previously developed compact indexes for tandem extraction. The notions and bounds provided for tandem motifs are generalized for the case r ⩾ 2, if r is the number of subwords composing the motifs. Finally, we also provide an algorithm to extract irredundant tandem motifs.

I&C Journal 2012 Journal Article

Combinatorial Pattern Matching (CPM 2010)

• Amihood Amir
• Laxmi Parida

Combinatorial Pattern Matching (CPM) addresses issues of searching and matching strings and more complicated structures such as trees, regular expressions, graphs, point sets, and arrays, in various formats. The goal is to derive non-trivial combinatorial properties of such structures and exploit these properties in order to achieve superior performance for the corresponding computational problems. However, another important goal is to analyze and pinpoint the properties and conditions under which searches cannot be performed efficiently. Over the past few decades a steady flow of high-quality research on this subject has changed a sparse set of isolated results into a full-fledged area of algorithmics. This area is continuing to grow even further due to the increasing demand for speed and efficiency that stems from important applications such as the World Wide Web, computational biology, computer vision, and multimedia systems. These involve requirements for information retrieval in heterogeneous databases, data compression and pattern recognition. The field has produced a large number of excellent new researchers, books, and conferences. One of the first conferences in the area was the Combinatorial Pattern Matching (CPM) conference. The objective of the annual CPM gathering is to provide an international forum for research in combinatorial pattern matching and related applications. The first twenty one meetings were held in Paris, London, Tucson, Padova, Asilomar, Helsinki, Laguna Beach, Aarhus, Piscataway, Warwick, Montreal, Jerusalem, Fukuka, Morelia, Istanbul, Jeju Island, Barcelona, London (Ontario), Pisa, Lille, Brooklyn, and Palermo over the years 1990–2011. After the first meeting, a selection of papers appeared as a special issue of Theoretical Computer Science in volume 92. The proceedings of the third to twenty first meetings appeared in the Springer LNCS series. The general organization and orientation of the CPM conferences is coordinated by a steering committee composed of Alberto Apostolico, Maxime Crochemore, and Zvi Galil. The papers contained in this volume were chosen from the abstracts presented at the 20th Annual Symposium on Combinatorial Pattern Matching, held June 21–23, 2010 at NYU-Poly in Brooklyn, New York. The conference was supported by NYU-Poly, The Center for Advanced Technology in Telecommunication (CATT) and IBM Research. Twenty eight extended abstracts were chosen after a refereeing process, and three presentations were invited to the conference. Those abstracts appeared in the symposium proceedings Springer LNCS 6129. Authors of the seven best ranked conference papers were invited to submit their papers to this special issue of Information and Computation. The papers went through a thorough review and the results appear in this volume.

TCS Journal 2008 Journal Article

Detection of subtle variations as consensus motifs

• Matteo Comin
• Laxmi Parida

We address the problem of detecting consensus motifs, that occur with subtle variations, across multiple sequences. These are usually functional domains in DNA sequences such as transcriptional binding factors or other regulatory sites. The problem in its generality has been considered difficult and various benchmark data serve as the litmus test for different computational methods. We present a method centered around unsupervised combinatorial pattern discovery. The parameters are chosen using a careful statistical analysis of consensus motifs. This method works well on the benchmark data and is general enough to be extended to a scenario where the variation in the consensus motif includes indels (along with mutations). We also present some results on detection of transcription binding factors in human DNA sequences.

TCS Journal 2008 Journal Article

Motif patterns in 2D

• Alberto Apostolico
• Laxmi Parida
• Simona E. Rombo

Motif patterns consisting of sequences of intermixed solid and don’t-care characters have been introduced and studied in connection with pattern discovery problems of computational biology and other domains. In order to alleviate the exponential growth of such motifs, notions of maximal saturation and irredundancy have been formulated, whereby more or less compact subsets of the set of all motifs can be extracted, that are capable of expressing all others by suitable combinations. In this paper, we introduce the notion of maximal irredundant motifs in a two-dimensional array and develop initial properties and a combinatorial argument that poses a linear bound on the total number of such motifs. The remainder of the paper presents approaches to the discovery of irredundant motifs both by offline and incremental algorithms.

TCS Journal 2005 Journal Article

An inexact-suffix-tree-based algorithm for detecting extensible patterns

• Abhijit Chattaraj
• Laxmi Parida

Given an input sequence of data, a rigid pattern is a repeating sequence, possibly interspersed with dont-care characters. The data could be a sequence of characters or sets of characters or even real values. In practice, the patterns or motifs of interest are the ones that also allow a variable number of gaps (or dont-care characters): these are patterns with spacers termed extensible patterns In a bioinformatics context, similar patterns have also been called flexible patterns or motifs. The extensibility is succinctly defined by a single integer parameter D ⩾ 1 which is interpreted as the allowable space to be between 1 and D characters between two successive solid characters in a reported motif. We introduce a data structure called the inexact-suffix tree and present an algorithm based on this data structure. This has been tested on primarily biological data such as DNA and protein sequences. However the generality of the system makes it equally applicable in other data mining, clustering, and knowledge extraction applications.

AAAI Conference 2005 Conference Paper

Redescription Mining: Structure Theory and Algorithms

• Laxmi Parida

We introduce a new data mining problem—redescription mining—that unifies considerations of conceptual clustering, constructive induction, and logical formula discovery. Redescription mining begins with a collection of sets, views it as a propositional vocabulary, and identifies clusters of data that can be defined in at least two ways using this vocabulary. The primary contributions of this paper are conceptual and theoretical: (i) we formally study the space of redescriptions underlying a dataset and characterize their intrinsic structure, (ii) we identify impossibility as well as strong possibility results about when mining redescriptions is feasible, (iii) we present several scenarios of how we can custom-build redescription mining solutions for various biases, and (iv) we outline how many problems studied in the larger machine learning community are really special cases of redescription mining. By highlighting its broad scope and relevance, we aim to establish the importance of redescription mining and make the case for a thrust in this new line of research.

SODA Conference 2000 Conference Paper

Pattern discovery on character sets and real-valued data: linear bound on irredundant motifs and an efficient polynomial time algorithm

• Laxmi Parida
• Isidore Rigoutsos
• Aris Floratos
• Daniel E. Platt
• Yuan Gao