A unifying framework for seed sensitivity and its application to subset seeds.

Gregory Kucherov; Laurent Noé; Mihkail Roytberg

hal-00018114, version 2

A unifying framework for seed sensitivity and its application to subset seeds.

Gregory Kucherov () ^1, 2, Laurent Noé ( Auteur à contacter de préférence ) ^1, 2, Mihkail Roytberg () ³

Journal of Bioinformatics and Computational Biology 4, 2 (2006) 553-69

Résumé : We propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem--a set of target alignments, an associated probability distribution, and a seed model--that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.

1 : Laboratoire d'Informatique Fondamentale de Lille (LIFL)
CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – INRIA
2 : SEQUOIA (INRIA Lille - Nord Europe)
INRIA – CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales
3 : Institute of Mathematical Problems in Biology (IMPB RAS)
Russian Academy of Science

hal-00018114, version 2
http://hal.archives-ouvertes.fr/hal-00018114
oai:hal.archives-ouvertes.fr:hal-00018114
Contributeur : Laurent Noé <>
Soumis le : Jeudi 14 Septembre 2006, 17:58:36
Dernière modification le : Jeudi 21 Juillet 2011, 14:13:44

Voir la fiche détaillée

Documents associés

PDF :

PS :

arXiv : cs.DS/0601116

PubMed : 16819802

PubMed Central : 2824148

DOI : 10.1142/S0219720006001977

Exporter

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="hal-00018114"><analytic>
<author><persName><forename>Gregory</forename><surname>Kucherov</surname></persName>
<affiliation>
<orgName type="laboratory">LIFL</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale de Lille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</orgName>
<orgName type="team">SEQUOIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
</affiliation>
</author>
<author><persName><forename>Laurent</forename><surname>Noé</surname></persName>
<affiliation>
<orgName type="laboratory">LIFL</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale de Lille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</orgName>
<orgName type="team">SEQUOIA</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
</affiliation>
</author>
<author><persName><forename>Mihkail</forename><surname>Roytberg</surname></persName>
<affiliation>
<orgName type="laboratory">IMPB RAS</orgName>
<orgName type="team">Institute of Mathematical Problems in Biology</orgName>
<country>RU</country>
<orgName type="institution">Russian Academy of Science</orgName>
</affiliation>
</author>
<title type="main" level="a">A unifying framework for seed sensitivity and its application to subset seeds.</title></analytic><monogr><title level="j" type="main">Journal of Bioinformatics and Computational Biology</title><imprint><biblScope type="publicationDate">2006-04-00</biblScope><biblScope type="vol">4</biblScope><biblScope type="issue">2</biblScope><biblScope type="pp">553-69</biblScope></imprint></monogr><idno type="doi">10.1142/S0219720006001977</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00018114</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00018114/PDF/paper.pdf</idno></biblStruct>
</listBibl>
</listBibl>