Fast computation of good multiple spaced seeds

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

Homology search finds similar segments between two biological sequences, such as DNA or protein sequences. A significant fraction of computing power in the world is dedicated to performing such tasks. The introduction of optimal spaced seeds by Ma et al. has increased both the sensitivity and the speed of homology search and it has been adopted by many alignment programs such as BLAST. With the further improvement provided by multiple spaced seeds in PatternHunterII, the sensitivity of dynamic programming is approached at BLASTn speed. Whereas computing optimal multiple spaced seeds was proved to be NP-hard, we show that, from practical point of view, computing good ones can be very efficient. We give a simple heuristic algorithm which computes good multiple seeds in polynomial time. Computing sensitivity is not required. When allowing the computation of the sensitivity for few seeds, we obtain better multiple seeds than previous ones in much shorter time.

Details

Authors
  • Lucian Ilie
  • Silvana Ilie
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Mathematics

Keywords

  • BLAST, PatternHunterII, string overlaps, sensitivity, homology search, multiple spaced seeds
Original languageEnglish
Title of host publicationAlgorithms in Bioinformatics, Proceedings (Lecture Notes in Computer Science)
PublisherSpringer
Pages346-358
Volume4645
ISBN (Print)978-3-540-74125-1
Publication statusPublished - 2007
Publication categoryResearch
Peer-reviewedYes
Event7th International Workshop on Algorithms in Bioinformatics (WABI 2007) - Philadelphia, Pennsylvania, United States
Duration: 2007 Sep 82007 Sep 9

Publication series

Name
Volume4645
ISSN (Print)1611-3349
ISSN (Electronic)0302-9743

Conference

Conference7th International Workshop on Algorithms in Bioinformatics (WABI 2007)
CountryUnited States
CityPhiladelphia, Pennsylvania
Period2007/09/082007/09/09

Bibliographic note

The information about affiliations in this record was updated in December 2015. The record was previously connected to the following departments: Numerical Analysis (011015004)