14 citations · 71 across the 21 of their papers we have counts for
11 papers · 1 filter
MSPP: A Highly Efficient and Scalable Algorithm for Mining Similar Pairs of Points
Subrata Saha, Ahmed Soliman, Sanguthevar Rajasekaran
The closest pair of points problem or closest pair problem (CPP) is an important problem in computational geometry where we have to find a pair of points from a set of points in me…
On pattern matching with k mismatches and few don't cares
Marius Nicolae, Sanguthevar Rajasekaran
We consider the problem of pattern matching with mismatches, where there can be don't care or wild card characters in the pattern. Specifically, given a pattern of length $…
Efficient Algorithms for the Closest Pair Problem and Applications
Sanguthevar Rajasekaran, Sudipta Pathak
The closest pair problem (CPP) is one of the well studied and fundamental problems in computing. Given a set of points in a metric space, the problem is to identify the pair of clo…
An error correcting parser for context free grammars that takes less than cubic time
Sanguthevar Rajasekaran, Marius Nicolae
The problem of parsing has been studied extensively for various formal grammars. Given an input string and a grammar, the parsing problem is to check if the input string belongs to…
An Elegant Algorithm for the Construction of Suffix Arrays
Sanguthevar Rajasekaran, Marius Nicolae
The suffix array is a data structure that finds numerous applications in string processing problems for both linguistic texts and biological data. It has been introduced as a memor…
On string matching with k mismatches
Marius Nicolae, Sanguthevar Rajasekaran
In this paper we consider several variants of the pattern matching problem. In particular, we investigate the following problems: 1) Pattern matching with k mismatches; 2) Approxim…
Efficient Sequential and Parallel Algorithms for Planted Motif Search
Marius Nicolae, Sanguthevar Rajasekaran
Motif searching is an important step in the detection of rare events occurring in a set of DNA or protein sequences. One formulation of the problem is known as (l,d)-motif search o…
A memory-efficient data structure representing exact-match overlap graphs with application for next generation DNA assembly
Hieu Dinh, Sanguthevar Rajasekaran
An exact-match overlap graph of given strings of length is an edge-weighted graph in which each vertex is associated with a string and there is an edge of weight…
An Efficient Algorithm For Chinese Postman Walk on Bi-directed de Bruijn Graphs
Vamsi Kundeti, Sanguthevar Rajasekaran, Hieu Dinh
Sequence assembly from short reads is an important problem in biology. It is known that solving the sequence assembly problem exactly on a bi-directed de Bruijn graph or a string g…
On the Border Length Minimization Problem (BLMP) on a Square Array
Vamsi Kundeti, Sanguthevar Rajasekaran, Hieu Dinh
Protein/Peptide microarrays are rapidly gaining momentum in the diagnosis of cancer. High-density and highthroughput peptide arrays are being extensively used to detect tumor bioma…
Efficient Parallel and Out of Core Algorithms for Constructing Large Bi-directed de Bruijn Graphs
Vamsi Kundeti, Sanguthevar Rajasekaran, Hieu Dinh
Assembling genomic sequences from a set of overlapping reads is one of the most fundamental problems in computational biology. Algorithms addressing the assembly problem fall into…