Arrow Research search

Author name cluster

Fatima Vayani

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

EAAI Journal 2016 Journal Article

Linear algorithm for conservative degenerate pattern matching

  • Maxime Crochemore
  • Costas S. Iliopoulos
  • Ritu Kundu
  • Manal Mohamed
  • Fatima Vayani

A degenerate symbol x ˜ over an alphabet Σ is a non-empty subset of Σ, and a sequence of such symbols is a degenerate string. A degenerate string is said to be conservative if its number of non-solid symbols is upper-bounded by a fixed positive constant k. We consider here the matching problem of conservative degenerate strings and present the first linear-time algorithm that can find, for given degenerate strings P ˜ and T ˜ of total length n containing k non-solid symbols in total, the occurrences of P ˜ in T ˜ in O(nk) time.

Details DOI

TCS Journal 2016 Journal Article

Linear-time superbubble identification algorithm for genome assembly

  • Ljiljana Brankovic
  • Costas S. Iliopoulos
  • Ritu Kundu
  • Manal Mohamed
  • Solon P. Pissis
  • Fatima Vayani

DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble. In this paper, we propose an O ( n + m ) -time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O ( m log ⁡ m ) -time algorithm by Sung et al.

Details DOI
v2026.09.13