NDLI: An optimized filter for finding multiple repeats in DNA sequences

Content Provider	IEEE Xplore Digital Library
Author	Federico, M. Peterlongo, P. Pisanti, N.
Copyright Year	2010
Description	Author affiliation: Dipartimento di ingegneria Informatica, Università di Modena e Reggio Emilia, Italy (Federico, M.) \|\| Dipartimento di Informatica, Università di Pisa, Italy (Pisanti, N.) \|\| EPI Symbiose, Centre Inria Rennes - Bretagne Atlantique, campus de Beaulieu, France (Peterlongo, P.)
Abstract	This paper presents new optimizations designed to improve an algorithm at the state-of-the-art for filtering sequences as a preprocessing step to the task of finding multiple repeats allowing a given pairwise edit distance between pairs of occurrences. The target application is to find possibly long repeats having two or more occurrences, such that each couple of occurrences may show substitutions, insertions or deletions in up to 10 to 15 % of their size. Assimilated to multiple alignment, exact detection of multiple repeats is an NP-hard problem. For increasing computation speed while avoiding the use of heuristics, one may use filters that quickly remove large parts of input that do not contain searched repeats. We describe at theoretical level some optimizations that can be applied to the tool that is currently the state-of-the-art for this filtering task. Finally, we exhibit some experiments in which the optimized tool outperforms its original version.
Starting Page	1
Ending Page	8
File Size	486304
Page Count	8
File Format	PDF
ISBN	9781424477166
e-ISBN	9781424477173
DOI	10.1109/AICCSA.2010.5587026
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-05-16
Publisher Place	Tunisia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Silicon Optimization Algorithm design and analysis Electronic mail DNA Hamming distance
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Optimized Algorithm for Finding Approximate Tandem Repeats in DNA Sequences

The research of codeword problem in DNA computing

The Optimization of DNA Encoding Sequences Based on Improved AFS Algorithms

DNA repeats detection using numerical representations and dot plot analysis

Evolutionary optimization programming with probabilistic models

Improved Genetic Algorithm for Designing DNA Sequences

Fast Motif Selection for Biological Sequences

A Bee Swarm Genetic Algorithm for the Optimization of DNA Encoding

Towards a general-purpose sequence design system in DNA computing

An optimized filter for finding multiple repeats in DNA sequences

Similar Documents

An Optimized Algorithm for Finding Approximate Tandem Repeats in DNA Sequences

The research of codeword problem in DNA computing

The Optimization of DNA Encoding Sequences Based on Improved AFS Algorithms

DNA repeats detection using numerical representations and dot plot analysis

Evolutionary optimization programming with probabilistic models

Improved Genetic Algorithm for Designing DNA Sequences

Fast Motif Selection for Biological Sequences

A Bee Swarm Genetic Algorithm for the Optimization of DNA Encoding

Towards a general-purpose sequence design system in DNA computing

An optimized filter for finding multiple repeats in DNA sequences