spaced_seeds.bib
@inproceedings{GambinEtAlBIOSTEC11,
author = {Gambin, Anna and Lasota, S{\l}awomir and Startek, Micha{\l} and Sykulski, Macieij and No{\'e}, Laurent and Kucherov, Gregory},
title = {Subset seed extension to {P}rotein {BLAST}},
booktitle = {Proceedings of the International Conference on Bioinformatics Models, Methods and Algorithms (BIOINFORMATICS 2011), January 26-29 2011, Rome (Italy)},
pages = {149--158},
month = {January},
year = {2011},
abstract = {The seeding technique became central in the theory of
sequence alignment and there are several efficient tools applying seeds to DNA
homology search. Recently, a concept of subset seeds has been proposed for
similarity search in protein sequences. We experimentally evaluate the
applicability of subset seeds to protein homology search. We advocate the use
of multiple subset seeds derived from a hierarchical tree of amino acid
residues. Our method computes, by an evolutionary algorithm, seeds that are
specifically designed for a given protein family. The representation of seeds
by deterministic finite automata (DFAs) is developed and built into the
NCBI-BLAST software. This extended tool, named SeedBLAST, is compared to the
original NCBI-BLAST on the GPCR protein family. Our results demonstrate a clear
superiority of SeedBLAST in terms of efficiency, especially in the case of
twilight zone hits. SeedBLAST is an open source software freely available
http://bioputer.mimuw.edu.pl/papers/sblast. Supplementary material and user
manual are also provided.},
doi = {10.5220/0003147601490158},
pdf = {http://www.lifl.fr/~noe/files/pp_BIOSTEC11.pdf},
hal-url = {http://hal.inria.fr/inria-00609791/en/},
opteditor = {},
optvolume = {},
optnumber = {},
optseries = {},
optaddress = {},
optorganization = {},
publisher = {{S}ci{T}e{P}ress Digital Library},
optnote = {},
optannote = {}
}
@article{NoeGirdeaKucherovABI10,
author = {No{\'e}, Laurent and G{\^i}rdea, Marta and Kucherov, Gregory},
title = {Designing efficient spaced seeds for {SOLiD} read mapping},
journal = {Advances in Bioinformatics},
year = {2010},
month = {July},
volume = {2010},
pages = {ID 708501},
doi = {10.1155/2010/708501},
url = {http://www.hindawi.com/journals/abi/2010/708501/},
pdf = {http://downloads.hindawi.com/journals/abi/2010/708501.pdf},
hal-url = {http://hal.inria.fr/inria-00527029/en/},
pubmed-url = {http://www.ncbi.nlm.nih.gov/pubmed/20936175},
pmc-url = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2945724},
opteprint = {},
abstract = {The advent of high-throughput sequencing technologies
constituted a major advance in genomic studies, offering new prospects in a
wide range of applications.We propose a rigorous and flexible algorithmic
solution to mapping SOLiD color-space reads to a reference genome. The solution
relies on an advanced method of seed design that uses a faithful probabilistic
model of read matches and, on the other hand, a novel seeding principle
especially adapted to read mapping. Our method can handle both lossy and
lossless frameworks and is able to distinguish, at the level of seed design,
between SNPs and reading errors. We illustrate our approach by several seed
designs and demonstrate their efficiency.},
inria = {Sequoia},
labo = {dans},
x-editorial-board = {yes},
x-international-audience = {yes},
x-pays = {RU},
aeres = {ACL},
selectif = {oui}
}
@inproceedings{NoeGirdeaKucherovRECOMB10,
author = {No{\'e}, Laurent and G{\^i}rdea, Marta and Kucherov, Gregory},
title = {Seed design framework for mapping {SOLiD} reads},
booktitle = {Proceedings of the 14th Annual International Conference on Research in Computational Molecular Biology ({RECOMB}), April 25-28, 2010, Lisbon (Portugal)},
pages = {384--396},
year = {2010},
month = {April},
editor = {Berger, B.},
volume = {6044},
series = {Lecture Notes in Computer Science},
doi = {10.1007/978-3-642-12683-3_25},
url = {http://www.springerlink.com/content/41535x341gu34131/},
pdf = {http://www.lifl.fr/~noe/files/pp_RECOMB10.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_RECOMB10.ps.gz},
hal-url = {http://hal.inria.fr/inria-00484642/en/},
optpubmed-url = {},
eprint = {1006.2625},
abstract = {The advent of high-throughput sequencing technologies
constituted a major advance in genomic studies, offering new prospects in a
wide range of applications. We propose a rigorous and flexible algorithmic
solution to mapping SOLiD color-space reads to a reference genome. The solution
relies on an advanced method of seed design that uses a faithful probabilistic
model of read matches and, on the other hand, a novel seeding principle
especially adapted to read mapping. Our method can handle both lossy and
lossless frameworks and is able to distinguish, at the level of seed design,
between SNPs and reading errors. We illustrate our approach by several seed
designs and demonstrate their efficiency.},
publisher = {Springer},
inria = {Sequoia},
labo = {dans},
x-editorial-board = {yes},
x-international-audience = {yes},
x-pays = {RU},
aeres = {ACT},
selectif = {oui},
optnote = {(submitted: 176, accepted: 36, acceptance rate: 0.20)}
}
@article{RoytbergEtAlTCBB09,
author = {Roytberg, Mikhail A. and Gambin, Anna and No{\'e}, Laurent and
Lasota, S{\l}awomir and Furletova, Eugenia and Szczurek, Ewa and
Kucherov, Gregory},
title = {On subset seeds for protein alignment},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)},
year = {2009},
month = {July},
pages = {483--494},
volume = {6},
number = {3},
doi = {10.1109/TCBB.2009.4},
url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4752807},
url = {http://doi.ieeecomputersociety.org/10.1109/tcbb.2009.4},
pdf = {http://www.lifl.fr/~noe/files/pp_TCBB09_preprint.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_TCBB09_preprint.ps.gz},
hal-url = {http://hal.inria.fr/inria-00354773/en/},
pubmed-url = {http://www.ncbi.nlm.nih.gov/pubmed/19644175},
eprint = {0901.3198},
abstract = {We apply the concept of subset seeds proposed in [1] to
similarity search in protein sequences. The main question studied is the design
of efficient seed alphabets to construct seeds with optimal
sensitivity/selectivity trade-offs. We propose several different design methods
and use them to construct several alphabets. We then perform a comparative
analysis of seeds built over those alphabets and compare them with the standard
BLASTP seeding method [2], [3], as well as with the family of vector seeds
proposed in [4]. While the formalism of subset seeds is less expressive (but
less costly to implement) than the cumulative principle used in BLASTP and
vector seeds, our seeds show a similar or even better performance than BLASTP
on Bernoulli models of proteins compatible with the common BLOSUM62 matrix.
Finally, we perform a large-scale benchmarking of our seeds against several
main databases of protein alignments. Here again, the results show a comparable
or better performance of our seeds vs. BLASTP.},
inria = {Sequoia},
labo = {dans},
x-editorial-board = {yes},
x-international-audience = {yes},
x-pays = {RU,PL},
aeres = {ACL},
selectif = {oui}
}
@inproceedings{RoytbergEtAlALBIO08,
author = {Roytberg, Mikhail A. and Gambin, Anna and No{\'e}, Laurent and Lasota, S{\l}awomir and Furletova, Eugenia and Szczurek, Ewa and Kucherov, Gregory},
title = {Efficient seeding techniques for protein similarity search},
booktitle = {Bioinformatics Research and Development, Proceedings of the 2nd International Conference BIRD 2008, Vienna (Austria), July 7-9, 2008},
pages = {466--478},
year = {2008},
month = {July},
editor = {Elloumi, M and K\"{u}ng, J. and Linial, M. and Murphy, R.F. and Schneider, K. and Toma, C.},
volume = {13},
series = {Communications in Computer and Information Science},
publisher = {Springer},
doi = {10.1007/978-3-540-70600-7_36},
url = {http://www.springerlink.com/content/m3560l36r573xjr5},
hal-url = {http://hal.inria.fr/inria-00335564/en/},
eprint = {0810.5434},
pdf = {http://www.lifl.fr/~noe/files/pp_ALBIO08.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_ALBIO08.ps.gz},
abstract = {We apply the concept of subset seeds proposed in [A unifying
framework for seed sensitivity and its application to subset seeds] to
similarity search in protein sequences. The main question studied is the
design of efficient seed alphabets to construct seeds with optimal sensitivity/
selectivity trade-offs. We propose several different design methods
and use them to construct several alphabets.We then perform an analysis
of seeds built over those alphabet and compare them with the standard
Blastp seeding method [2,3], as well as with the family of vector seeds
proposed in [4]. While the formalism of subset seed is less expressive
(but less costly to implement) than the accumulative principle used in
Blastp and vector seeds, our seeds show a similar or even better performance
than Blastp on Bernoulli models of proteins compatible with
the common BLOSUM62 matrix.},
inria = {Sequoia},
labo = {dans},
x-editorial-board = {yes},
x-international-audience = {yes},
x-proceedings = {yes},
x-pays = {RU,PL},
aeres = {ACT},
selectif = {non},
optnote = {(submitted: 61, accepted: 30, acceptance rate: 0.50)}
}
@inproceedings{KucherovNoeRoytbergCIAA07,
author = {Kucherov, Gregory and No{\'e}, Laurent and Roytberg, Mikhail A.},
title = {Subset Seed Automaton},
booktitle = {Proceedings of the 12th International {C}onference on
{I}mplementation and {A}pplication of {A}utomata ({CIAA}), July 16-18, 2007, Prague (Czech Republic)},
pages = {180--191},
year = {2007},
month = {July},
editor = {Holub, J. and Zdarek, J.},
volume = {4783},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
doi = {10.1007/978-3-540-76336-9_18},
url = {http://www.springerlink.com/content/y824l20554002756},
pdf = {http://www.lifl.fr/~noe/files/pp_CIAA07.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_CIAA07.ps.gz},
hal-url = {http://hal.inria.fr/inria-00170414/en/},
opteprint = {},
abstract = {We study the pattern matching automaton introduced in
[Kucherov-Noe-Roytberg-JBCB-06] for the purpose of seed-based similarity
search. We show that our definition provides a compact automaton, much smaller
than the one obtained by applying the Aho-Corasick construction. We study
properties of this automaton and present an efficient implementation of the
automaton construction. We also present some experimental results and show that
this automaton can be successfully applied to more general situations.},
inria = {Sequoia},
labo = {dans},
x-editorial-board = {yes},
x-international-audience = {yes},
x-proceedings = {yes},
x-pays = {RU},
aeres = {ACT},
selectif = {oui},
optnote = {(submitted: 79, accepted: 23, acceptance rate: 0.29)}
}
@inproceedings{PeterlongoEtAlPBC07,
author = {Peterlongo, Pierre and No{\'e}, Laurent and Lavenier, Dominique and Georges, Gilles and Jacques, Julien and Kucherov, Gregory and Giraud, Mathieu},
title = {Protein similarity search with subset seeds on a dedicated reconfigurable hardware},
booktitle = {Proceedings of the 2nd Workshop on {P}arallel {B}io-{C}omputing (PBC), September 9-12, 2007 Gdansk (Poland)},
pages = {1240--1248},
year = {2008},
month = {September},
editor = {Wyrzykowski, R. and Dongarra, J. and Karczewski, K. and Wasniewski, J.},
volume = {4967},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
doi = {10.1007/978-3-540-68111-3},
pdf = {http://www.lifl.fr/~giraud/publis/peterlongo-pbc-07.pdf},
url = {http://www.springerlink.com/content/2280v0131631528r},
hal-url = {http://hal.inria.fr/inria-00178325/en/},
opteprint = {},
abstract = {With a sharp increase of available DNA and protein sequence
data, new precise and fast similarity search methods are needed for largescale
genome and proteome comparisons. Modern seed-based techniques
of similarity search (spaced seeds, multiple seeds, subset seeds) provide
a better sensitivity/specificity ratio. We present an implementation of
such a seed-based technique on a parallel specialized hardware embedding
reconfigurable architecture (FPGA), where the FPGA is tightly
connected to large capacity Flash memories. This parallel system allows
large databases to be fully indexed and rapidly accessed. Compared to
traditional approaches presented by the Blastp software, we obtain both
a significant speed-up and better results. To the best of our knowledge,
this is the first attempt to exploit efficient seed-based algorithms for
parallelizing the sequence similarity search.},
inria = {Sequoia},
labo = {dans},
x-editorial-board = {yes},
x-international-audience = {yes},
x-proceedings = {yes},
aeres = {ACT},
selectif = {oui}
}
@article{KucherovNoeRoytbergJBCB06,
author = {Kucherov, Gregory and No{\'e}, Laurent and Roytberg, Mikhail A.},
title = {A unifying framework for seed sensitivity and its application to subset seeds},
journal = {Journal of Bioinformatics and Computational Biology},
year = {2006},
month = {November},
volume = {4},
number = {2},
pages = {553--569},
doi = {10.1142/S0219720006001977},
url = {http://www.worldscinet.com/jbcb/04/0402/S0219720006001977.html},
hal-url = {http://hal.archives-ouvertes.fr/hal-00018114},
pubmed-url = {http://www.ncbi.nlm.nih.gov/pubmed/16819802},
pmc-url = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC2824148},
eprint = {cs.DS/0601116},
postscript = {http://www.lifl.fr/~noe/files/pp_JBCB06_preprint.ps.gz},
pdf = {http://www.lifl.fr/~noe/files/pp_JBCB06_preprint.pdf},
abstract = {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
{\em 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.},
inria = {Sequoia},
labo = {dans},
x-editorial-board = {yes},
x-international-audience = {yes},
x-pays = {RU},
aeres = {ACL},
selectif = {oui}
}
@inproceedings{KucherovNoeRoytbergWABI05,
author = {Kucherov, Gregory and No{\'e}, Laurent and Roytberg, Mikhail A.},
title = {A unifying framework for seed sensitivity and its application to subset seeds},
booktitle = {Proceedings of the 5th International Workshop on Algorithms in Bioinformatics ({WABI}), October 3-6, 2005, Mallorca (Spain)},
pages = {251--263},
year = {2005},
month = {October},
editor = {Casadio, R and Myers, G},
volume = {3692},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
doi = {10.1007/11557067_21},
url = {http://springerlink.metapress.com/content/72384x40t0v2j254/},
hal-url = {http://hal.inria.fr/inria-00001164/en/},
eprint = {cs.OH/0603106},
pdf = {http://www.lifl.fr/~noe/files/pp_WABI05.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_WABI05.ps.gz},
abstract = {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
{\em 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.},
inria = {ADAGE},
labo = {hors},
x-editorial-board = {yes},
x-international-audience = {yes},
x-proceedings = {yes},
x-pays = {RU},
aeres = {ACT},
selectif = {oui},
optnote = {(submitted: 94, accepted: 35, acceptance rate: 0.37)}
}
@article{NoeKucherovNAR05,
author = {No{\'e}, Laurent and Kucherov, Gregory},
title = {{YASS}: enhancing the sensitivity of {DNA} similarity search},
journal = {Nucleic Acids Research},
year = {2005},
month = {April},
volume = {33 (web-server issue)},
number = {suppl\_2},
pages = {W540--W543},
doi = {10.1093/nar/gki478},
url = {http://nar.oxfordjournals.org/cgi/content/abstract/33/suppl_2/W540},
pdf = {http://nar.oxfordjournals.org/cgi/reprint/33/suppl_2/W540.pdf},
hal-url = {http://hal.inria.fr/inria-00448742/en/},
pubmed-url = {http://www.ncbi.nlm.nih.gov/pubmed/15980530},
pmc-url = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1160238},
opteprint = {},
abstract = {YASS is a DNA local alignment tool based on an efficient and
sensitive filtering algorithm. It applies transition-constrained seeds to
specify the most probable conserved motifs between homologous sequences,
combined with a flexible hit criterion used to identify groups of seeds that are
likely to exhibit significant alignments. A web interface
(http://www.loria.fr/projects/YASS/) is available to upload input sequences in
fasta format, query the program and visualize the results obtained in several
forms (dot-plot, tabular output and others). A standalone version is available
for download from the web page.},
inria = {ADAGE},
labo = {hors},
x-editorial-board = {yes},
x-international-audience = {yes},
aeres = {ACL},
selectif = {oui}
}
@article{KucherovNoeRoytbergTCBB05,
author = {Kucherov, Gregory and No{\'e}, Laurent and Roytberg, Mikhail A.},
title = {Multiseed lossless filtration},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)},
pages = {51--61},
year = {2005},
month = {January},
key = {ISSN:1545-5963},
volume = {2},
number = {1},
doi = {10.1109/tcbb.2005.12},
url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1416851},
url = {http://doi.ieeecomputersociety.org/10.1109/tcbb.2005.12},
hal-url = {http://hal.inria.fr/inria-00354810/en/},
pubmed-url = {http://www.ncbi.nlm.nih.gov/pubmed/17044164},
eprint = {0901.3215},
pdf = {http://www.lifl.fr/~noe/files/pp_TCBB05_preprint.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_TCBB05_preprint.ps.gz},
abstract = {We study a method of seed-based lossless filtration for
approximate string matching and related bioinformatics applications. The method
is based on a simultaneous use of several spaced seeds rather than a single seed
as studied by Burkhardt and Karkkainen. We present algorithms to compute several
important parameters of seed families, study their combinatorial properties, and
describe several techniques to construct efficient families. We also report a
large-scale application of the proposed technique to the problem of
oligonucleotide selection for an {EST} sequence database.},
inria = {ADAGE},
labo = {hors},
x-editorial-board = {yes},
x-international-audience = {yes},
aeres = {ACL},
selectif = {oui}
}
@phdthesis{NoePHD05,
author = {No{\'e}, Laurent},
title = {Recherche de similarit{\'e}s dans les s{\'e}quences d'ADN:
mod{\`e}les et algorithmes pour la conception de graines efficaces},
school = {Universit{\'e} Henri Poincar{\'e} - Nancy},
year = {2005},
month = {September},
pdf = {http://www.lifl.fr/~noe/files/phd.pdf},
postscript = {http://www.lifl.fr/~noe/files/phd.ps.gz},
hal-url = {http://tel.archives-ouvertes.fr/tel-00011482},
opteprint = {},
abstract = {Les m{\'e}thodes de recherche de similarit{\'e}s les plus
fr{\'e}quemment utilis{\'e}es dans le cadre de la g{\'e}nomique sont
heuristiques. Elles se basent sur un principe de filtrage du texte qui permet
de localiser les r{\'e}gions potentiellement similaires.
Dans cette th{\`e}se, nous proposons de nouvelles d{\'e}finitions de filtres
pour la recherche de similarit{\'e}s sur les s{\'e}quences g{\'e}nomiques et
des algorithmes associ{\'e}s pour mesurer leurs caract{\'e}ristiques. Plus
pr{\'e}cis{\'e}ment, nous avons {\'e}tudi{\'e} le mod{\`e}le des {\em graines
espac{\'e}es}, et propos{\'e} un algorithme d'{\'e}valuation de l'efficacit{\'e}
des graines sur des similarit{\'e}s d'une classe particuli{\`e}re
(similarit{\'e}s dites {\em homog{\`e}nes}). Nous avons {\'e}galement
d{\'e}velopp{\'e} un algorithme g{\'e}n{\'e}ral pour la mesure de
l'efficacit{\'e} des graines, ainsi qu'un nouveau mod{\`e}le de graine
appel{\'e} {\em graine sous-ensemble}, extension du mod{\`e}le des {\em graines
espac{\'e}es}. Enfin nous donnons, dans le cadre du {\em filtrage sans perte},
une extension {\`a} l'aide de graines multiples, que nous analysons et
appliquons au probl{\`e}me de la conception d'oligonucl{\'e}otides.
Nous avons r{\'e}alis{\'e} et donnons acc{\`e}s {\`a} des outils pour la
conception des filtres, ainsi que pour la recherche de similarit{\'e}s.},
aeres = {TH},
labo = {hors},
inria = {ADAGE}
}
@inproceedings{KucherovNoeRoytbergCPM04,
author = {Kucherov, Gregory and No{\'e}, Laurent and Roytberg, Mikhail A.},
title = {Multi-seed lossless filtration},
booktitle = {Proceedings of the 15th Annual Combinatorial Pattern Matching Symposium (CPM), July 5-7, 2004, Istanbul (Turkey)},
pages = {297--310},
year = {2004},
month = {July},
editor = {Sahinalp, S.C. and Muthukrishnan, S. and Dogrusoz, U.},
volume = {3109},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
doi = {10.1007/978-3-540-27801-6_22},
url = {http://www.springerlink.com/content/hrw7dvbn8ua9q6ly},
pdf = {http://www.lifl.fr/~noe/files/pp_CPM04.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_CPM04.ps.gz},
hal-url = {http://hal.inria.fr/inria-00001162/en/},
opteprint = {},
isnb = {3-540-22341-X},
abstract = {We study a method of seed-based lossless filtration for
approximate string matching and related bioinformatics applications. The method
is based on a simultaneous use of several spaced seeds rather than a single
seed as studied by Burkhardt and Karkkainen. We present algorithms to compute
several important parameters of seed families, study their combinatorial
properties, and describe several techniques to construct efficient families. We
also report a large-scale application of the proposed technique to the problem
of oligonucleotide selection for an {EST} sequence database.},
inria = {ADAGE},
labo = {hors},
x-editorial-board = {yes},
x-international-audience = {yes},
x-proceedings = {yes},
aeres = {ACT},
selectif = {oui},
optnote = {(submitted: 79, accepted: 36, acceptance rate: 0.46)}
}
@inproceedings{KucherovNoePontyBIBE04,
author = {Kucherov, Gregory and No{\'e}, Laurent and Ponty, Yann},
title = {Estimating seed sensitivity on homogeneous alignments},
booktitle = {Proceedings of the IEEE 4th Symposium on Bioinformatics and Bioengineering (BIBE), May 19-21, 2004, Taichung (Taiwan)},
pages = {387--394},
year = {2004},
month = {April},
opteditor = {},
optvolume = {},
optnumber = {},
optseries = {the IEEE 4th Symposium on Bioinformatics and Bioengineering - BIBE'2004},
optaddress = {},
optorganization = {},
publisher = {IEEE Computer Society Press},
doi = {10.1109/BIBE.2004.1317369},
url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1317369},
url = {http://doi.ieeecomputersociety.org/10.1109/BIBE.2004.1317369},
pdf = {http://www.lifl.fr/~noe/files/pp_BIBE04.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_BIBE04.ps.gz},
hal-url = {http://hal.inria.fr/inria-00001163/en/},
eprint = {cs.OH/0603106},
abstract = {We address the problem of estimating the sensitivity of
seed-based similarity search algorithms. In contrast to approaches based on
Markov models [Faster and more sensitive homology search, Designing seeds for
similarity search in genomic DNA, Optimal spaced seeds for Hidden Markov Models,
with application to homologous coding regions, Vector seeds: an extension to
spaced seeds allows substantial improvements in sensitivity and specificity,
Sensitivity analysis and efficient method for identifying optimal spaced seeds],
we study the estimation based on homogeneous alignments. We describe an
algorithm for counting and random generation of those alignments and an
algorithm for exact computation of the sensitivity for a broad class of seed
strategies. We provide experimental results demonstrating a bias introduced by
ignoring the homogeneousness condition.},
inria = {ADAGE},
labo = {hors},
x-editorial-board = {yes},
x-international-audience = {yes},
x-proceedings = {yes},
aeres = {ACT},
selectif = {oui},
optnote = {(submitted: 145, accepted: 71, acceptance rate: 0.49)}
}
@article{NoeKucherovBMCBioinformatics04,
author = {No{\'e}, Laurent and Kucherov, Gregory},
title = {Improved hit criteria for {DNA} local alignment},
journal = {{BMC} {B}ioinformatics},
year = {2004},
volume = {5},
pages = {149},
month = {October},
doi = {10.1186/1471-2105-5-149},
url = {http://www.biomedcentral.com/1471-2105/5/149},
pdf = {http://www.biomedcentral.com/content/pdf/1471-2105-5-149.pdf},
hal-url = {http://hal.inria.fr/inria-00448743/en/},
pubmed-url = {http://www.ncbi.nlm.nih.gov/pubmed/15485572},
pmc-url = {http://www.ncbi.nlm.nih.gov/pmc/articles/PMC526756},
opteprint = {},
abstract = {Background: the hit criterion is a key component of heuristic
local alignment algorithms. It specifies a class of patterns assumed to witness
a potential similarity, and this choice is decisive for the selectivity and
sensitivity of the whole method.
Results : in this paper, we propose two ways to improve the hit criterion.
First, we define the group criterion combining the advantages of the
single-seed and double-seed approaches used in existing algorithms. Second, we
introduce transition-constrained seeds that extend spaced seeds by the
possibility of distinguishing transition and transversion mismatches. We provide
analytical data as well as experimental results, obtained with the YASS
software, supporting both improvements.
Conclusions : proposed algorithmic ideas allow to obtain a significant gain in
sensitivity of similarity search without increase in execution time. The method
has been implemented in YASS software available at
http://www.loria.fr/projects/YASS/},
inria = {ADAGE},
labo = {hors},
x-editorial-board = {yes},
x-international-audience = {yes},
aeres = {ACL},
selectif = {oui}
}
@inproceedings{NoeKucherovJOBIM04,
author = {No{\'e}, Laurent and Kucherov, Gregory},
title = {Improved hit criteria for {DNA} local alignment},
booktitle = {Proceedings of the 5th Open Days in Biology, Computer Science and Mathematics (JOBIM), June 28-30, 2004, Montr\'eal (Canada)},
year = {2004},
month = {June},
pdf = {http://www.lifl.fr/~noe/files/pp_JOBIM04.pdf},
postscript = {http://www.lifl.fr/~noe/files/pp_JOBIM04.ps.gz},
hal-url = {http://hal.inria.fr/inria-00099999/en/},
abstract = {The hit criterion is a key component of heuristic local
alignment algorithms. It specifies a class of patterns assumed to witness a
potential similarity, and this choice is decisive for the selectivity and
sensitivity of the whole method. In this paper, we propose two ways to improve
the hit criterion. First, we define the group criterion combining the advantages
of the single-seed and double-seed approaches used in existing algorithms.
Second, we introduce transition-constrained seeds that extend spaced seeds by
the possibility of distinguishing transition and transversion mismatches. We
provide analytical data as well as experimental results, obtained with our YASS
software, supporting both improvements.}
}
@phdthesis{BrejovaPHD05,
author = {Brejov{\'a}, Bro{\v{n}}a},
title = {Evidence Combination in Hidden Markov Models for Gene Prediction},
school = {University of Waterloo},
year = {2005},
pdf = {http://etd.uwaterloo.ca/etd/bbrejova2005.pdf}
}
@article{MarshallHermsKaltenbachRahmannTCBB12,
author = {Marschall, Tobias and Herms, Inke and Kaltenbach, Hans-Michael and Rahmann, Sven},
title = {Probabilistic Arithmetic Automata and their Applications},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)},
year = {2012},
optkey = {},
optvolume = {},
optnumber = {},
optpages = {},
optmonth = {},
note = {(to appear)},
optannote = {},
doi = {10.1109/TCBB.2012.109}
}
@inproceedings{AcoSeedANTS12,
author = {Do Duc, Dong and Dinh, Huy Q. and Dang, Thanh Hai and Laukens, Kris and Hoang, Xuan Huan},
title = {{A}co{S}ee{D}: An Ant Colony Optimization for Finding Optimal Spaced Seeds in Biological Sequence Search},
booktitle = {Proceedings of the 8th International Conference on Swarm Intelligence (ANTS), Brussels (Belgium)},
pages = {204--211},
year = {2012},
opteditor = {},
volume = {7461},
series = {Lecture Notes in Computer Science},
optmonth = {},
optaddress = {},
optorganization = {},
publisher = {Springer},
url = {http://www.springerlink.com/content/n1476j612302410k/},
pdf = {http://www.springerlink.com/content/n1476j612302410k/fulltext.pdf},
doi = {10.1007/978-3-642-32650-9_19}
}
@article{IlieBMCResearchNotes12,
author = {Ilie, Silvana},
title = {Efficient Computation of Spaced Seeds},
journal = {{BMC} {R}esearch {N}otes},
year = {2012},
volume = {5},
number = {123},
url = {http://www.biomedcentral.com/1756-0500/5/123},
pdf = {http://www.biomedcentral.com/content/pdf/1756-0500-5-123.pdf},
doi = {10.1186/1756-0500-5-123}
}
@inproceedings{EgidiManziniSPIRE11,
author = {Egidi, Lavinia and Manzini, Giovanni},
title = {Spaced Seeds Design Using Perfect Rulers},
booktitle = {Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE), Pisa (Italy)},
pages = {32-43},
year = {2011},
opteditor = {},
volume = {7024},
series = {Lecture Notes in Computer Science},
optaddress = {},
optmonth = {},
optorganization = {},
publisher = {Springer},
url = {http://www.springerlink.com/content/c18m78j1214h7k21/},
pdf = {http://www.springerlink.com/content/c18m78j1214h7k21/fulltext.pdf},
doi = {10.1007/978-3-642-24583-1_5}
}
@article{ChenSheZhuCSB11,
author = {Chen, Ke and She, Kun and Zhu, QingXin},
title = {Overlap digraph: An effective model for finding good spaced seeds for biological sequence local alignment},
journal = {Chinese Science Bulletin},
year = {2011},
volume = {56},
number = {11},
pages = {1100--1107},
url = {http://www.springerlink.com/content/ar2700j0106h8062},
pdf = {http://www.springerlink.com/content/ar2700j0106h8062/fulltext.pdf},
doi = {10.1007/s11434-010-4161-9}
}
@article{IlieEtAlBioinformatics11,
author = {Ilie, Lucian and Ilie, Silvana and Mansouri Bigvand, Anahita},
title = {{SpEED}: fast computation of sensitive spaced seeds},
journal = {Bioinformatics},
year = {2011},
volume = {27},
number = {17},
pages = {2433--2434},
doi = {10.1093/bioinformatics/btr368},
url = {http://bioinformatics.oxfordjournals.org/content/27/17/2433},
pdf = {http://bioinformatics.oxfordjournals.org/content/27/17/2433.full.pdf}
}
@article{IlieEtAlBMCGenomics11,
author = {Ilie, Lucian and Ilie, Silvana and Khoshraftar, Shima and Mansouri Bigvand, Anahita},
title = {Seeds for Effective Oligonucleotide Design},
journal = {{BMC} {G}enomics},
year = {2011},
volume = {12},
pages = {280},
url = {http://www.biomedcentral.com/1471-2164/12/280},
pdf = {http://www.biomedcentral.com/content/pdf/1471-2164-12-280.pdf},
doi = {10.1186/1471-2164-12-280}
}
@article{KielbasaWanSatoHortonFrithGENOMERESEARCH11,
author = {Kie{\l}basa, Szymon M. and Wan, Raymond and Sato, Kengo and Horton, Paul and Frith, Martin C.},
title = {Adaptive seeds tame genomic sequence comparison},
journal = {Genome Research},
year = {2011},
volume = {21},
number = {3},
pages = {487--493},
url = {http://genome.cshlp.org/content/21/3/487},
pdf = {http://genome.cshlp.org/content/21/3/487.pdf},
doi = {10.1101/gr.113985.110}
}
@article{ZhouMihaiFloreaCIS10,
author = {Zhou, Leming and Mihai, Ingrid and Florea, Liliana},
title = {Spaced Seeds for Cross-species {cDNA}-to-genome Sequence Alignment},
journal = {Communications in Information and Systems},
year = {2010},
volume = {10},
number = {2},
pages = {115--136},
url = {http://projecteuclid.org/euclid.cis/1268143267},
pdf = {http://www.ims.cuhk.edu.hk/~cis/2010.2/CIS_10_2_04.pdf}
}
@article{ChungParkAPBC10,
author = {Chung, Won-Hyoung and Park, Seong-Bae},
title = {Hit integration for identifying optimal spaced seeds},
journal = {{BMC} {B}ioinformatics - Selected articles from the 8th Asia-Pacific Bioinformatics Conference (APBC), 18-21 january, Bangalore, India},
year = {2010},
volume = {11},
number = {Suppl 1},
pages = {S37},
url = {http://www.biomedcentral.com/1471-2105/11/S1/S37},
pdf = {http://www.biomedcentral.com/content/pdf/1471-2105-11-S1-S37.pdf},
doi = {10.1186/1471-2105-11-S1-S37}
}
@article{ChungParkBMCGenomics09,
author = {Chung, Won-Hyoung and Park, Seong-Bae},
title = {An empirical study of choosing efficient discriminative seeds for oligonucleotide design},
journal = {{BMC} {G}enomics},
year = {2009},
volume = {10},
number = {Suppl 3},
pages = {S3},
url = {http://www.biomedcentral.com/1471-2164/10/S3/S3},
pdf = {http://www.biomedcentral.com/content/pdf/1471-2164-10-S3-S3.pdf},
doi = {10.1186/1471-2164-10-S3-S3}
}
@article{NguyenLavenierBMCBioinformatics09,
author = {Nguyen, Van-Hoa and Lavenier, Dominique},
title = {{PLAST}: parallel local alignment search tool for database comparison},
journal = {{BMC} {B}ioinformatics},
year = {2009},
volume = {10},
pages = {329},
url = {http://www.biomedcentral.com/1471-2105/10/329},
pdf = {http://www.biomedcentral.com/content/pdf/1471-2105-10-329.pdf},
doi = {10.1186/1471-2105-10-329}
}
@article{ChenSouaiaiaChenBioinformatics09,
author = {Chen, Yangho and Souaiaia, Tate and Chen, Ting},
title = {{P}er{M}: efficient mapping of short sequencing reads with periodic full sensitive spaced seeds},
journal = {Bioinformatics},
year = {2009},
volume = {25},
number = {19},
pages = {2514--2521},
url = {http://bioinformatics.oxfordjournals.org/content/25/19/2514},
pdf = {http://bioinformatics.oxfordjournals.org/content/25/19/2514.full.pdf},
doi = {10.1093/bioinformatics/btp486}
}
@article{ChenZhuYangTangCSB09,
author = {Chen, Ke and Zhu, QingXin and Yang, Fan and Tang, DongMing},
title = {An efficient way of finding good indel seeds for local homology search},
journal = {Chinese Science Bulletin},
year = {2009},
volume = {54},
number = {20},
pages = {3837--3842},
url = {http://www.springerlink.com/content/2761735rp606whm3},
pdf = {http://www.springerlink.com/content/2761735rp606whm3/fulltext.pdf},
doi = {10.1007/s11434-009-0531-6}
}
@article{MaYaoIPL09,
author = {Ma, Bin and Yao, Hongyi},
title = {Seed optimization for i.i.d. similarities is no easier than optimal {G}olomb ruler design},
journal = {Information Processing Letters},
year = {2009},
volume = {109},
number = {19},
pages = {1120--1124},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0020019009002270},
doi = {10.1016/j.ipl.2009.07.008},
note = {(earlier version in APBC 2008)}
}
@inproceedings{LiMaZhangBICOB09,
author = {Li, Weiming and Ma, Bin and Zhang, Kaizhong},
title = {Amino Acid Classification and Hash Seeds for Homology Search},
booktitle = {Proceedings of the 1st International Conference in Bioinformatics and Computational Biology, BICoB 2009, New Orleans, LA, USA},
pages = {44--51},
year = {2009},
volume = {5462},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/tw16158h62304766},
pdf = {http://www.springerlink.com/content/tw16158h62304766/fulltext.pdf},
doi = {10.1007/978-3-642-00727-9_6}
}
@article{IlieIlieBioinformatics09,
author = {Ilie, Lucian and Ilie, Silvana},
title = {Fast computation of neighbor seeds},
journal = {Bioinformatics},
year = {2009},
volume = {25},
number = {6},
pages = {822--823},
url = {http://bioinformatics.oxfordjournals.org/content/25/6/822},
pdf = {http://bioinformatics.oxfordjournals.org/content/25/6/822.full.pdf},
doi = {10.1093/bioinformatics/btp054}
}
@article{MakBensonBioinformatics09,
author = {Mak, Denise Y.F. and Benson, Gary},
title = {All hits all the time: parameter free calculation of seed sensitivity},
journal = {Bioinformatics},
year = {2009},
volume = {25},
number = {3},
pages = {302--308},
note = {(earlier version in APBC 2007)},
url = {http://bioinformatics.oxfordjournals.org/content/25/3/302},
pdf = {http://bioinformatics.oxfordjournals.org/content/25/3/302.full.pdf},
doi = {10.1093/bioinformatics/btn643}
}
@book{ChaoZhangBook08,
author = {Chao, Kun-Mao and Zhang, Louxin},
title = {Sequence Comparison: Theory and Methods},
publisher = {Springer},
year = {2008},
key = {978-1-84800-319-4},
volume = {7},
series = {Computational Biology},
url = {http://www.springer.com/computer/bioinformatics/book/978-1-84800-319-4},
doi = {10.1007/978-1-84800-320-0}
}
@inproceedings{LavenierIPDPS08,
author = {Lavenier, Dominique},
title = {Ordered Index Seed Algorithm for Intensive {DNA} Sequence Comparison},
booktitle = {IEEE International Symposium on Parallel and Distributed Processing (IPDPS)},
pages = {1--8},
year = {2008},
doi = {10.1109/IPDPS.2008.4536172},
pdf = {http://hal.archives-ouvertes.fr/docs/00/32/26/96/PDF/lavenier_1569087275.pdf}
}
@inproceedings{BensonMakSPIRE08,
author = {Benson, Gary and Mak, Denise Y.F.},
title = {Exact Distribution of a Spaced Seed Statistic for {DNA} Homology Detection},
booktitle = {Proceedings of the 15th International Symposium on String Processing and Information Retrieval (SPIRE), Melbourne (Australia)},
pages = {282--293},
year = {2008},
editor = {Amir, A. and Turpin, A. and Moffat, A.},
volume = {5280},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/m8875971g270t7n3/fulltext.pdf},
pdf = {http://www.springerlink.com/content/m8875971g270t7n3},
doi = {10.1007/978-3-540-89097-3_27}
}
@inproceedings{NguyenLavenierRIVF08,
author = {Nguyen, Van-Hoa and Lavenier, Dominique},
title = {Speeding up Subset Seed Algorithm for Intensive Protein Sequence Comparison},
booktitle = {Proceedings of the 6th IEEE International Conference on research, innovation \& vision for the future},
pages = {57--63},
year = {2008},
url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=4586333},
doi = {10.1109/RIVF.2008.4586333}
}
@article{YangZhangJCB08,
author = {Yang, Jialiang and Zhang, Louxin},
title = {Run Probabilities of Seed-Like Patterns and Identifying Good Transition Seeds},
journal = {Journal of Computational Biology},
year = {2008},
volume = {15},
number = {10},
pages = {1295--1313},
month = {Dec.},
note = {(earlier version in APBC 2008)},
url = {http://www.liebertonline.com/doi/abs/10.1089/cmb.2007.0209},
pdf = {http://www.liebertonline.com/doi/pdf/10.1089/cmb.2007.0209},
doi = {10.1089/cmb.2007.0209}
}
@article{NicolasRivalsJCSS08,
author = {Nicolas, Fran{\c{c}}ois and Rivals, {\'E}ric},
title = {Hardness of Optimal Spaced Seed Design},
journal = {Journal of Computer and System Sciences},
year = {2008},
volume = {74},
number = {5},
month = {Aug.},
pages = {831--849},
note = {(earlier version in CPM 2005)},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0022000007001444},
pdf = {http://www.lirmm.fr/~rivals/PUBLI/FILES/NR-seeds-preprint-121007.pdf},
doi = {10.1016/j.jcss.2007.10.001}
}
@inproceedings{HermsRahmannWABI08,
author = {Herms, Inke and Rahmann, Sven},
title = {Computing Alignment Seed Sensitivity with Probabilistic Arithmetic Automata},
booktitle = {Proceedings of the 8th International Workshop on Algorithms in Bioinformatics ({WABI}), Karlsruhe (Germany)},
pages = {318--329},
year = {2008},
volume = {5251},
month = {Sept.},
series = {Lecture Notes in Bioinformatics},
publisher = {Springer},
url = {http://www.springerlink.com/content/e8w1g39288144l56},
url = {http://www.springerlink.com/content/e8w1g39288144l56/fulltext.pdf},
doi = {10.1007/978-3-540-87361-7_27}
}
@article{LinZhangZhangMaLiBioinformatics08,
author = {Lin, Hao and Zhang, Zefeng and Zhang, Michael Q. and Ma, Bin and Li, Ming},
title = {{ZOOM!} {Z}illions {O}f {O}ligos {M}apped},
journal = {Bioinformatics},
year = {2008},
volume = {24},
number = {21},
pages = {2431--2437},
url = {http://bioinformatics.oxfordjournals.org/content/24/21/2431},
pdf = {http://bioinformatics.oxfordjournals.org/content/24/21/2431.full.pdf},
doi = {10.1093/bioinformatics/btn416}
}
@article{ZhouStantonFloreaBMCBioinformatics08,
author = {Zhou, Leming and Stanton, Jonathan and Florea, Liliana},
title = {Universal seeds for c{DNA}-to-genome comparison},
journal = {{BMC} {B}ioinformatics},
year = {2008},
volume = {9},
pages = {36},
url = {http://www.biomedcentral.com/1471-2105/9/36},
pdf = {http://www.biomedcentral.com/content/pdf/1471-2105-9-36.pdf},
doi = {10.1186/1471-2105-9-36}
}
@inproceedings{YangZhangAPBC08,
author = {Yang, Jialiang and Zhang, Louxin},
title = {Run Probability of High-Order Seed Patterns and its Applications to Finding Good Transition Seeds},
booktitle = {Proceedings of the 6th Asia Pacific Bioinformatics Conference (APBC), 14-17 January 2008, Kyoto, Japan},
pages = {123--132},
year = {2008},
editor = {Brazma, A. and Miyano, S. and Akutsu, T.},
volume = {6},
series = {Advances in Bioinformatics and Computational Biology},
publisher = {Imperial College Press},
url = {http://eproceedings.worldscinet.com/9781848161092/9781848161092_0015.html},
pdf = {http://www.comp.nus.edu.sg/~wongls/psZ/apbc2008/apbc056a.pdf},
doi = {10.1142/9781848161092_0015}
}
@inproceedings{MaYaoAPBC08,
author = {Ma, Bin and Yao, Hongyi},
title = {Seed Optimization Is No Easier than Optimal {G}olomb Ruler Design},
booktitle = {Proceedings of the 6th Asia Pacific Bioinformatics Conference (APBC), 14-17 January 2008, Kyoto, Japan},
pages = {133--144},
editor = {Brazma, A. and Miyano, S. and Akutsu, T.},
year = {2008},
volume = {6},
series = {Advances in Bioinformatics and Computational Biology},
publisher = {Imperial College Press},
url = {http://eproceedings.worldscinet.com/9781848161092/9781848161092_0016.html},
doi = {10.1142/9781848161092_0016}
}
@inbook{BrownBA08,
author = {Brown, Daniel G.},
title = {Bioinformatics Algorithms: Techniques and Applications},
chapter = {A survey of seeding for sequence alignment},
publisher = {Wiley-Interscience (I. Mandoiu, A. Zelikovsky)},
year = {2008},
month = {Fev.},
pages = {126--152},
url = {http://www.bioinformatics.uwaterloo.ca/papers/07seeds.pdf},
optdoi = {}
}
@article{ZhangLinLiJBCB08,
author = {Zhang, Zefeng and Lin, Hao and Li, Ming},
title = {{M}ango: multiple alignment with {N} gapped oligos},
journal = {Journal of Bioinformatics and Computational Biology},
year = {2008},
volume = {6},
number = {3},
pages = {521--541},
month = {June},
url = {http://www.worldscinet.com/jbcb/06/0603/S0219720008003527.html},
pdf = {http://www.worldscinet.com/jbcb/06/preserved-docs/0603/S0219720008003527.pdf},
doi = {10.1142/S0219720008003527}
}
@inproceedings{ZhangLinLiCSB07,
author = {Zhang, Zefeng and Lin, Hao and Li, Ming},
title = {{M}ango: A new approach to multiple sequence alignment},
booktitle = {Proceedings of the 6th International Conference on Computational Systems Bioinformatics (CSB), San Diego, USA},
pages = {237--247},
year = {2007},
volume = {6},
month = {August},
pdf = {http://www.lifesciencessociety.org/CSB2007/toc/PDF/237.2007.pdf},
url = {http://www.lifesciencessociety.org/CSB2007/toc/237.2007.html}
}
@inproceedings{GaoLiLuFAW07,
author = {Gao, Xin and Li, Shuai Cheng and Lu, Yinan},
title = {New Algorithms for the Spaced Seeds},
booktitle = {Frontiers of Algorithmic Workshop 2007 (FAW2007)},
pages = {51--61},
year = {2007},
volume = {4613},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/f446r56013x7w852},
pdf = {http://www.springerlink.com/content/f446r56013x7w852/fulltext.pdf},
doi = {10.1007/978-3-540-73814-5_5}
}
@inproceedings{IlieIlieBIOCOMP07,
author = {Ilie, Lucian and Ilie, Silvana},
title = {Long spaced seeds for finding similarities between biological sequences},
booktitle = {Proceedings of the 2nd International Conference on Bioinformatics {\&} Computational Biology (BIOCOMP)},
year = {2007},
pages = {3--8},
pdf = {http://www.csd.uwo.ca/faculty/ilie/BIOCOMP07.pdf},
optdoi = {}
}
@inproceedings{DuchesneGiraudElMabroukCOCOON07,
author = {Duchesne, Jean-Eudes and Giraud, Mathieu and El-Mabrouk, Nadia},
title = {Seed-Based Exclusion Method for Non-coding {RNA} Gene Search},
booktitle = {Proceedings of the 13rd International Computing and Combinatorics Conference ({COCOON})},
pages = {27--39},
year = {2007},
volume = {4598},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/r2n71753j7q5mm07},
pdf = {http://www.springerlink.com/content/r2n71753j7q5mm07/fulltext.pdf},
doi = {10.1007/978-3-540-73545-8_6}
}
@article{IlieIlieBioinformatics07,
author = {Ilie, Lucian and Ilie, Silvana},
title = {Multiple spaced seeds for homology search},
journal = {Bioinformatics},
year = {2007},
volume = {23},
number = {22},
pages = {2969--2977},
month = {Sept.},
url = {http://bioinformatics.oxfordjournals.org/content/23/22/2969},
pdf = {http://bioinformatics.oxfordjournals.org/content/23/22/2969.full.pdf},
doi = {10.1093/bioinformatics/btm422}
}
@inproceedings{IlieIlieWABI07,
author = {Ilie, Lucian and Ilie, Silvana},
title = {Fast computation of good multiple spaced seeds},
booktitle = {Proceedings of the 7th International Workshop on Algorithms in Bioinformatics ({WABI}), Philadelphia ({USA})},
pages = {346--358},
year = {2007},
month = {Sept.},
volume = {4645},
series = {Lecture Notes in Bioinformatics},
publisher = {Springer},
url = {http://www.springerlink.com/content/a13453hv4t53j470},
pdf = {http://www.springerlink.com/content/a13453hv4t53j470/fulltext.pdf},
doi = {10.1007/978-3-540-74126-8_32}
}
@article{ZhangTCBB07,
author = {Zhang, Louxin},
title = {Superiority of Spaced Seeds for Homology Search},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)},
year = {2007},
volume = {4},
number = {3},
pages = {496--505},
url = {http://doi.ieeecomputersociety.org/10.1109/tcbb.2007.1013},
doi = {10.1109/tcbb.2007.1013}
}
@article{MaLiJCSS07,
author = {Ma, Bin and Li, Ming},
title = {On the complexity of spaced seeds},
journal = {Journal of Computer and System Sciences},
year = {2007},
volume = {73},
number = {7},
pages = {1024--1034},
month = {Mar.},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0022000007000268},
doi = {10.1016/j.jcss.2007.03.008}
}
@article{FarachEtAlJCSS07,
author = {Farach-Colton, Martin and Landau, Gad M. and Cenk Sahinalp, S{\"u}leyman and Tsur, Dekel},
title = {Optimal spaced seeds for faster approximate string matching},
journal = {Journal of Computer and System Sciences},
year = {2007},
volume = {73},
number = {7},
pages = {1035--1044},
month = {Nov.},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0022000007000256},
doi = {10.1016/j.jcss.2007.03.007}
}
@article{FengTillierBioinformatics07,
author = {Feng, Shengzhong and Tillier, Elisabeth R.M.},
title = {A fast and flexible approach to oligonucleotide probe design for genomes and gene families},
journal = {Bioinformatics},
year = {2007},
volume = {23},
number = {10},
pages = {1195--1202},
url = {http://bioinformatics.oxfordjournals.org/content/23/10/1195},
pdf = {http://bioinformatics.oxfordjournals.org/content/23/10/1195.full.pdf},
doi = {10.1093/bioinformatics/btm114}
}
@article{KongJCB07,
author = {Kong, Yong},
title = {Generalized Correlation Functions and Their Applications in Selection of Optimal Multiple Spaced Seeds for Homology Search},
journal = {Journal of Computational Biology},
year = {2007},
volume = {14},
number = {2},
pages = {238--254},
month = {Mar.},
url = {http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.0008},
pdf = {http://www.liebertonline.com/doi/pdf/10.1089/cmb.2006.0008},
doi = {10.1089/cmb.2006.0008}
}
@article{ZhouFloreaJCB07,
author = {Zhou, Leming and Florea, Liliana},
title = {Designing sensitive and specific spaced seeds for cross-species m{RNA}-to-genome alignment},
journal = {Journal of Computational Biology},
year = {2007},
volume = {14},
number = {2},
pages = {113--130},
month = {Mar.},
url = {http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.0130},
pdf = {http://www.liebertonline.com/doi/pdf/10.1089/cmb.2006.0130},
doi = {10.1089/cmb.2006.0130}
}
@inproceedings{MakBensonAPBC07,
author = {Mak, Denise Y.F. and Benson, Gary},
title = {All hits all the time: parameter free calculation of seed sensitivity},
booktitle = {Proceedings of the 5th Asia Pacific Bioinformatics Conference (APBC)},
pages = {327--340},
editor = {Sankoff, D. and Wang, L. and Chin, F.},
year = {2007},
series = {Advances in Bioinformatics and Computational Biology},
volume = {5},
publisher = {Imperial College Press},
url = {http://eproceedings.worldscinet.com/9781860947995/9781860947995_0035.html},
pdf = {http://tandem.bu.edu/papers/all_hits_all_the_time.pdf},
doi = {10.1142/9781860947995_0035}
}
@article{XuBrownLiMaJCB06,
author = {Xu, Jinbo and Brown, Daniel G. and Li, Ming and Ma, Bin},
title = {Optimizing Multiple Spaced Seeds for Homology Search},
journal = {Journal of Computational Biology},
year = {2006},
volume = {13},
number = {7},
pages = {1355--1368},
url = {http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.13.1355},
pdf = {http://www.liebertonline.com/doi/pdf/10.1089/cmb.2006.13.1355},
doi = {10.1089/cmb.2006.13.1355},
note = {(earlier version in CPM 2004)}
}
@article{MakGelfandBensonBioinformatics06,
author = {Mak, Denise Y.F. and Gelfand, Yevgeniy and Benson, Gary},
title = {Indel seeds for homology search},
journal = {Bioinformatics},
year = {2006},
volume = {22},
number = {14},
pages = {e341--e349},
url = {http://bioinformatics.oxfordjournals.org/content/22/14/e341},
pdf = {http://bioinformatics.oxfordjournals.org/content/22/14/e341.full.pdf},
doi = {10.1093/bioinformatics/btl263}
}
@article{CsurosMaAlgorithmica07,
author = {Cs{\H{u}}r{\"o}s, Mikl{\'o}s and Ma, Bin},
title = {Rapid homology search with neighbor seeds},
journal = {Algorithmica},
year = {2007},
volume = {48},
number = {2},
pages = {187--202},
month = {Jun.},
url = {http://www.springerlink.com/content/45446712u14n0416},
pdf = {http://www.springerlink.com/content/45446712u14n0416/fulltext.pdf},
pdf = {http://www.iro.umontreal.ca/~csuros/papers/neighbor-seeds.pdf},
doi = {10.1007/s00453-007-0062-y},
note = {(earlier version in COCOON 2005)}
}
@inproceedings{DarlingTreangenZhangWABI06,
author = {Darling, Aaron E. and Treangen, Todd J. and Zhang, Louxin and Kuiken, Carla and Messeguer, Xavier and Perna, Nicole T.},
title = {Procrastination leads to efficient filtration for local multiple alignment},
booktitle = {Proceedings of the 6th International Workshop on Algorithms in Bioinformatics (WABI), Z\"{u}rich (Switzerland)},
pages = {126--137},
year = {2006},
volume = {4175},
series = {Lecture Notes in Bioinformatics},
month = {Sept.},
publisher = {Springer},
url = {http://www.springerlink.com/content/4624203q2421h34n},
pdf = {http://www.springerlink.com/content/4624203q2421h34n/fulltext.pdf},
pdf = {http://gel.ahabs.wisc.edu/procrastination/procrastination.pdf},
doi = {10.1007/11851561_12}
}
@article{SunBuhlerBMCBioinformatics06,
author = {Sun, Yanni and Buhler, Jeremy},
title = {Choosing the best heuristic for seeded alignment of {DNA} sequences},
journal = {{BMC} {B}ioinformatics},
year = {2006},
volume = {7},
pages = {133},
month = {Mar.},
url = {http://www.biomedcentral.com/1471-2105/7/133},
pdf = {http://www.biomedcentral.com/content/pdf/1471-2105-7-133.pdf},
doi = {10.1186/1471-2105-7-133}
}
@inproceedings{LiMaZhangSODA06,
author = {Li, Ming and Ma, Bin and Zhang, Louxin},
title = {Superiority and complexity of the Spaced Seeds},
booktitle = {Proceedings of the 17th Symposium on Discrete Algorithms (SODA)},
pages = {444--453},
year = {2006},
publisher = {ACM Press},
pdf = {http://www.math.nus.edu.sg/~matzlx/papers/Soda06.pdf},
url = {http://doi.acm.org/10.1145/1109557.1109607},
doi = {10.1145/1109557.1109607}
}
@article{ChoiZhangCOSMOS05,
author = {Choi, Kwok Pui and Zhang, Louxin},
title = {Analysis of Spaced Seed Technique in Sequence Alignment},
journal = {COSMOS},
year = {2005},
volume = {1},
number = {1},
pages = {57--73},
url = {http://www.worldscinet.com/cosmos/01/0101/S0219607705000048.html},
pdf = {http://www.worldscinet.com/cosmos/01/preserved-docs/0101/S0219607705000048.pdf},
doi = {10.1142/S0219607705000048}
}
@article{FlannickBatzoglouNAR05,
author = {Flannick, Jason and Batzoglou, Serafim},
title = {Using multiple alignments to improve seeded local alignment algorithms},
journal = {Nucleic Acids Research},
year = {2005},
volume = {33},
number = {14},
pages = {4563--4577},
url = {http://nar.oxfordjournals.org/cgi/content/abstract/33/14/4563},
doi = {10.1093/nar/gki767}
}
@inproceedings{PolKahveciBIBE05,
author = {Pol, Abhijit and Kahveci, Tamer},
title = {Highly Scalable and Accurate Seeds for Subsequence Alignments},
booktitle = {Proceedings of the IEEE 5th Symposium on Bioinformatics and Bioengineering (BIBE), Minneapolis (USA)},
pages = {27--31},
year = {2005},
publisher = {IEEE Computer Society Press},
url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1544445},
url = {http://doi.ieeecomputersociety.org/10.1109/BIBE.2005.37},
doi = {10.1109/BIBE.2005.37}
}
@article{FontaineBurkhardtKarkkainenIJFCS05,
author = {Fontaine, Marc and Burkhardt, Stefan and K{\"a}rkk{\"a}inen, Juha},
title = {{BDD}-Based Analysis of Gapped $q$-Gram Filters},
journal = {International Journal of Foundations of Computer Science},
year = {2005},
volume = {6},
number = {16},
pages = {1121--1134},
postscript = {http://www.cs.helsinki.fi/juha.karkkainen/publications/ijfcs05-preliminary.ps.gz},
doi = {10.1142/S0129054105003698},
note = {(earlier version is PSC 2004)}
}
@inproceedings{CsurosMaCOCOON05,
author = {Cs{\H{u}}r{\"o}s, Mikl{\'o}s and Ma, Bin},
title = {Rapid homology search with two-stage extension and daughter seeds},
booktitle = {Proceedings of the 11th International Computing and Combinatorics Conference ({COCOON})},
pages = {104--114},
year = {2005},
volume = {3595},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/258d5vqh76dyg2vy},
pdf = {http://www.springerlink.com/content/258d5vqh76dyg2vy/fulltext.pdf},
pdf = {http://www.iro.umontreal.ca/~csuros/papers/daughter-seeds.pdf},
doi = {10.1007/11533719_13}
}
@article{PreparataZhangChoiJCB05,
author = {Preparata, Franco P. and Zhang, Louxin and Choi, Kwok Pui},
title = {Quick, Practical Selection of Effective Seeds for Homology Search},
journal = {Journal of Computational Biology},
year = {2005},
volume = {12},
number = {9},
pages = {1137--1152},
url = {http://www.liebertonline.com/doi/abs/10.1089/cmb.2005.12.1137},
pdf = {http://www.liebertonline.com/doi/pdf/10.1089/cmb.2005.12.1137},
doi = {10.1089/cmb.2005.12.1137}
}
@article{BuhlerKeichSunJCSS05,
author = {Buhler, Jeremy and Keich, Uri and Sun, Yanni},
title = {Designing seeds for similarity search in genomic {DNA}},
journal = {Journal of Computer and System Sciences},
year = {2005},
volume = {70},
number = {3},
pages = {342--363},
pdf = {http://www.cs.cornell.edu/~keich/papers/Designing_seeds_for_similarity_search_in_genomic_DNA_JCSS05.pdf},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0022000004001515},
doi = {10.1016/j.jcss.2004.12.003},
note = {(earlier version in RECOMB 2003)}
}
@article{BrejovaBrownVinarJCSS05,
author = {Brejov{\'a}, Bro{\v{n}}a and Brown, Daniel G. and Vina{\v{r}}, Tom{\'a}{\v{s}}},
title = {Vector seeds: An extension to spaced seeds},
journal = {Journal of Computer and System Sciences},
year = {2005},
volume = {70},
number = {3},
pages = {364--380},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0022000004001527},
doi = {10.1016/j.jcss.2004.12.008},
note = {(earlier version in WABI 2003)}
}
@article{SunBuhlerJCB05,
author = {Sun, Yanni and Buhler, Jeremy},
title = {Designing Multiple Simultaneous Seeds for {DNA} Similarity Search},
journal = {Journal of Computational Biology},
volume = {12},
number = {6},
year = {2005},
pages = {847--861},
url = {http://www.liebertonline.com/doi/abs/10.1089/cmb.2005.12.847},
pdf = {http://www.liebertonline.com/doi/pdf/10.1089/cmb.2005.12.847},
doi = {10.1089/cmb.2005.12.847},
note = {(earlier version in RECOMB 2004)}
}
@inproceedings{FarachLandauICALP05,
author = {Farach-Colton, Martin and Landau, Gad M. and Cenk Sahinalp, S{\"u}leyman and Tsur, Dekel},
title = {Optimal spaced seeds for faster approximate string matching},
booktitle = {Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP'05), Lisboa (Portugal)},
pages = {1251--1262},
year = {2005},
volume = {3580},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/815pej6c1kc09upj},
pdf = {http://www.springerlink.com/content/815pej6c1kc09upj/fulltext.pdf},
doi = {10.1007/11523468_101}
}
@inproceedings{NicolasRivalsCPM05,
author = {Nicolas, Fran{\c{c}}ois and Rivals, {\'E}ric},
title = {Hardness of Optimal Spaced Seed Design},
booktitle = {Proceedings of the 16th Annual Symposium on Combinatorial Pattern Matching (CPM), Jeju Island (Korea)},
pages = {144--155},
year = {2005},
editor = {Apostolico, A. and Crochemore, M. and Park, K.},
volume = {3537},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/ybhxf0p3dgwwbe1x},
pdf = {http://www.springerlink.com/content/ybhxf0p3dgwwbe1x/fulltext.pdf},
doi = {10.1007/b137128}
}
@article{BrownTCBB05,
author = {Brown, Daniel G.},
title = {Optimizing Multiple Seeds for Protein Homology Search},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB)},
pages = {29--38},
year = {2005},
key = {ISSN:1545-5963},
volume = {2},
number = {1},
month = {january},
url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1416848},
url = {http://doi.ieeecomputersociety.org/10.1109/TCBB.2005.13},
doi = {10.1109/TCBB.2005.13},
note = {(earlier version in WABI 2004)}
}
@article{TPatternHunter05,
author = {Kisman, Derek and Li, Ming and Ma, Bin and Li, Wang},
title = {t{P}atternHunter: gapped, fast and sensitive translated homology search},
journal = {Bioinformatics},
year = {2005},
volume = {21},
number = {4},
pages = {542--544},
month = {February},
url = {http://bioinformatics.oxfordjournals.org/content/21/4/542},
pdf = {http://bioinformatics.oxfordjournals.org/content/21/4/542.full.pdf},
doi = {10.1093/bioinformatics/bti035}
}
@article{BrownLiMaJBCB04,
author = {Brown, Daniel G. and Li, Ming and Ma, Bin},
title = {A tutorial of recent developments in the seeding of local alignment},
journal = {Journal of Bioinformatics and Computational Biology},
year = {2004},
volume = {2},
number = {4},
pages = {819--842},
url = {http://www.worldscinet.com/jbcb/02/0204/S0219720004000983.html},
pdf = {http://www.worldscinet.com/jbcb/02/preserved-docs/0204/S0219720004000983.pdf},
pdf = {http://www.cs.ucdavis.edu/~gusfield/spring06readings/jbcbsurvey.pdf},
doi = {10.1142/S0219720004000983}
}
@inproceedings{FontaineBurkhardtKarkkainenPSC04,
author = {Fontaine, Marc and Burkhardt, Stefan and K{\"a}rkk{\"a}inen, Juha},
title = {{BDD}-Based Analysis of Gapped $q$-Gram Filters},
booktitle = {Proceedings of the 9th Prague Stringology Conference (PSC)},
pages = {56--68},
year = {2004},
url = {http://psc.felk.cvut.cz/event/2004/p5.html},
pdf = {http://www.stups.uni-duesseldorf.de/~fontaine/PSC2005.pdf}
}
@inproceedings{BrownHudekWABI04,
author = {Brown, Daniel G. and Hudek, Alexander K.},
title = {New Algorithms for Multiple {DNA} Sequence Alignment},
booktitle = {Proceedings of the 4th International Workshop on Algorithms in Bioinformatics (WABI), Bergen (Norway)},
pages = {314--325},
year = {2004},
editor = {Jonassen, I. and Kim, J.},
volume = {3240},
series = {Lecture Notes in Bioinformatics},
month = {September},
publisher = {Springer},
url = {http://www.springerlink.com/content/xgxrj97wf0fplpvd},
pdf = {http://www.springerlink.com/content/xgxrj97wf0fplpvd/fulltext.pdf},
doi = {10.1007/978-3-540-30219-3_27}
}
@inproceedings{BrownWABI04,
author = {Brown, Daniel G.},
title = {Multiple vector seeds for protein alignment},
booktitle = {Proceedings of the 4th International Workshop on Algorithms in Bioinformatics (WABI), Bergen (Norway)},
pages = {170--181},
year = {2004},
editor = {Jonassen, I. and Kim, J.},
volume = {3240},
series = {Lecture Notes in Bioinformatics},
month = {September},
publisher = {Springer},
url = {http://www.springerlink.com/content/ene216xh927j6btw},
pdf = {http://www.springerlink.com/content/ene216xh927j6btw/fulltext.pdf},
doi = {10.1007/978-3-540-30219-3_15}
}
@article{HuangYeChouEtAl2004,
author = {Huang, Xiaoqiu and Ye, Liang and Chou, Hui-Hsien and Yang, I-Hsuan and Chao, Kun-Mao},
title = {Efficient Combination of Multiple Word Models for Improved Sequence Comparison},
journal = {Bioinformatics},
year = {2004},
volume = {20},
number = {16},
pages = {2529--2533},
url = {http://bioinformatics.oxfordjournals.org/content/20/16/2529},
pdf = {http://bioinformatics.oxfordjournals.org/content/20/16/2529.full.pdf},
doi = {10.1093/bioinformatics/bth279}
}
@article{KeichLiMaTrompDAM04,
author = {Keich, Uri and Li, Ming and Ma, Bin and Tromp, John},
title = {On spaced seeds for similarity search},
journal = {Discrete Applied Mathematics},
year = {2004},
volume = {138},
number = {3},
pages = {253--263},
note = {(preliminary version in 2002)},
pdf = {http://monod.uwaterloo.ca/papers/04seeds.pdf},
doi = {10.1016/S0166-218X(03)00382-2}
}
@inproceedings{CsurosCPM04,
author = {Cs{\H{u}}r{\"o}s, Mikl{\'o}s},
title = {Performing Local Similarity Searches with Variable Length Seeds},
booktitle = {Proceedings of the 15th Annual Combinatorial Pattern Matching Symposium (CPM), Istanbul (Turkey)},
pages = {373--387},
year = {2004},
editor = {Sahinalp, S.C. and Muthukrishnan, S. and Dogrusoz, U.},
volume = {3109},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/r522bxk567yh1h5b},
pdf = {http://www.springerlink.com/content/r522bxk567yh1h5b/fulltext.pdf},
doi = {10.1007/978-3-540-27801-6_28}
}
@inproceedings{XuBrownLiMaCPM04,
author = {Xu, Jinbo and Brown, Daniel G. and Li, Ming and Ma, Bin},
title = {Optimizing multiple spaced seeds for homology search},
booktitle = {Proceedings of the 15th Symposium on Combinatorial Pattern Matching (CPM), Istambul (Turkey)},
pages = {47--58},
year = {2004},
editor = {Sahinalp, S.C. and Muthukrishnan, S. and Dogrusoz, U.},
volume = {3109},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.13.1355},
pdf = {http://www.liebertonline.com/doi/pdf/10.1089/cmb.2006.13.1355},
doi = {10.1089/cmb.2006.13.1355}
}
@inproceedings{YangWangChenEtAlBIBE04,
author = {Yang, I-Hsuan and Wang, Sheng-Ho and Chen, Yang-Ho and Huang, Pao-Hsian and Ye, Liang and Huang, Xiaoqiu and Chao, Kun-Mao},
title = {Efficient Methods for Generating Optimal Single and Multiple Spaced Seeds},
booktitle = {Proceedings of the IEEE 4th Symposium on Bioinformatics and Bioengineering (BIBE), Taichung (Taiwan)},
pages = {411--416},
year = {2004},
publisher = {IEEE Computer Society Press},
url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1317372},
url = {http://doi.ieeecomputersociety.org/10.1109/BIBE.2004.1317372},
doi = {10.1109/BIBE.2004.1317372}
}
@article{BrejovaBrownVinarJBCB04,
author = {Brejov{\'a}, Bro{\v{n}}a and Brown, Daniel G. and Vina{\v{r}}, Tom{\'a}{\v{s}}},
title = {Optimal spaced seeds for homologous coding regions},
journal = {Journal of Bioinformatics and Computational Biology},
year = {2004},
volume = {1},
number = {4},
pages = {595--610},
month = {Jan},
url = {http://www.worldscinet.com/jbcb/01/0104/S0219720004000326.html},
pdf = {http://www.worldscinet.com/jbcb/01/preserved-docs/0104/S0219720004000326.pdf},
doi = {10.1142/S0219720004000326}
}
@article{PatternHunter04,
author = {Li, Ming and Ma, Bin and Kisman, Derek and Tromp, John},
title = {{P}attern{H}unter {II}: Highly Sensitive and Fast Homology Search},
journal = {Journal of Bioinformatics and Computational Biology},
year = {2004},
volume = {2},
number = {3},
pages = {417--439},
note = {(earlier version in GIW 2003)},
url = {http://www.worldscinet.com/jbcb/02/0203/S0219720004000661.html},
doi = {10.1142/S0219720004000661}
}
@inproceedings{SunBuhlerRECOMB04,
author = {Sun, Yanni and Buhler, Jeremy},
title = {Designing multiple simultaneous seeds for {DNA} similarity search},
booktitle = {Proceedings of the 8th Annual International Conference on Research in Computational Molecular Biology (RECOMB), San Diego (California)},
pages = {76--84},
year = {2004},
month = {March},
url = {http://doi.acm.org/10.1145/974614.974625},
doi = {10.1145/974614.974625}
}
@article{ChoiZengZhangBioinformatics04,
author = {Choi, Kwok Pui and Zeng, Fanfan and Zhang, Louxin},
title = {Good Spaced Seeds For Homology Search},
journal = {Bioinformatics},
year = {2004},
volume = {20},
number = {7},
pages = {1053--1059},
url = {http://bioinformatics.oxfordjournals.org/content/20/7/1053},
pdf = {http://bioinformatics.oxfordjournals.org/content/20/7/1053.full.pdf},
doi = {10.1093/bioinformatics/bth037}
}
@article{ChoiZhangJCSS04,
author = {Choi, Kwok Pui and Zhang, Louxin},
title = {Sensitivity Analysis and Efficient Method for Identifying Optimal Spaced Seeds},
journal = {Journal of Computer and System Sciences},
year = {2004},
volume = {68},
number = {1},
pages = {22--40},
url = {http://linkinghub.elsevier.com/retrieve/pii/S0022000003001430},
doi = {10.1016/j.jcss.2003.04.002}
}
@article{ChenSungGI03,
author = {Chen, Wei and Sung, Wing-Kin},
title = {On Half Gapped Seed},
journal = {Genome Informatics},
year = {2003},
volume = {14},
pages = {176--185},
note = {preliminary version in the 14th International Conference on Genome Informatics (GIW)},
url = {http://sciencelinks.jp/j-east/article/200408/000020040804A0139350.php},
pdf = {http://www.jsbi.org/pdfs/journal1/GIW03/GIW03F018.pdf},
optdoi = {}
}
@inproceedings{BrejovaBrownVinarWABI03,
author = {Brejov{\'a}, Bro{\v{n}}a and Brown, Daniel G. and Vina{\v{r}}, Tom{\'a}{\v{s}}},
title = {Vector seeds: an extension to spaced seeds allows substantial improvements in sensitivity and specificity},
booktitle = {WABI},
pages = {39--54},
year = {2003},
volume = {2812},
series = {Lecture Notes in Computer Science},
month = {September},
publisher = {Springer},
url = {http://www.springerlink.com/content/u6fr322a7yfh6u7f},
pdf = {http://www.springerlink.com/content/u6fr322a7yfh6u7f/fulltext.pdf},
doi = {10.1007/978-3-540-39763-2_4}
}
@inproceedings{BuhlerKeichSunRECOMB03,
author = {Buhler, Jeremy and Keich, Uri and Sun, Yanni},
title = {Designing seeds for similarity search in genomic {DNA}},
booktitle = {Proceedings of the 7th Annual International Conference on Research in Computational Molecular Biology (RECOMB), Berlin (Germany)},
pages = {67--75},
year = {2003},
month = {April},
publisher = {ACM Press},
pdf = {http://www.cs.cornell.edu/~keich/papers/spaced_seeds_RECOMB03.pdf},
doi = {10.1145/640075.640083}
}
@article{BLASTZ03,
author = {Schwartz, Scott and Kent, W. James and Smit, Arian and Zhang, Zheng and Baertsch, Robert and Hardison, Ross C. and Haussler, David and Miller, Webb},
title = {Human--Mouse Alignments with {BLASTZ}},
journal = {Genome Research},
year = {2003},
volume = {13},
pages = {103--107},
url = {http://www.genome.org/cgi/content/abstract/13/1/103},
doi = {10.1101/gr.809403}
}
@inproceedings{BrejovaBrownVinarCPM03,
author = {Brejov{\'a}, Bro{\v{n}}a and Brown, Daniel G. and Vina{\v{r}}, Tom{\'a}{\v{s}}},
title = {Optimal Spaced Seeds for {H}idden {M}arkov {M}odels, with Application to Homologous Coding Regions},
booktitle = {Proceedings of the 14th Symposium on Combinatorial Pattern Matching (CPM), Morelia (Mexico)},
pages = {42--54},
year = {2003},
editor = {R. Baeza-Yates, E. Chavez, M. Crochemore},
volume = {2676},
series = {Lecture Notes in Computer Science},
month = {June},
publisher = {Springer},
url = {http://www.springerlink.com/content/95727262p4477810},
pdf = {http://www.springerlink.com/content/95727262p4477810/fulltext.pdf},
postscript = {http://www.bioinformatics.uwaterloo.ca/papers/03seeds.ps.gz},
doi = {10.1007/3-540-44888-8_4}
}
@article{BurkhardtKarkkainenFI03,
author = {Burkhardt, Stefan and K{\"a}rkk{\"a}inen, Juha},
title = {Better filtering with gapped $q$-grams},
journal = {Fundamenta Informaticae},
year = {2002},
volume = {56},
number = {1-2},
pages = {51--70},
note = {Preliminary version in Combinatorial Pattern Matching 2001},
url = {http://iospress.metapress.com/content/8ad9p3mqeday8vt5},
pdf = {http://iospress.metapress.com/content/8ad9p3mqeday8vt5/fulltext.pdf},
postscript = {http://www.cs.helsinki.fi/juha.karkkainen/publications/ijfcs05-preliminary.ps.gz}
}
@inproceedings{BurkhardtKarkkainenCPM02,
author = {Burkhardt, Stefan and K{\"a}rkk{\"a}inen, Juha},
title = {{O}ne-gapped $q$-gram filters for {L}evenshtein {D}istance},
booktitle = {Proceedings of the 13th Symposium on Combinatorial Pattern Matching (CPM)},
pages = {225--234},
year = {2002},
volume = {2373},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
url = {http://www.springerlink.com/content/dtbhuy9bcbc3hh2b},
pdf = {http://www.springerlink.com/content/dtbhuy9bcbc3hh2b/fulltext.pdf},
doi = {10.1007/3-540-45452-7_19}
}
@inproceedings{BuhlerRECOMB02,
author = {Buhler, Jeremy},
title = {Provably sensitive indexing strategies for biosequence similarity search},
booktitle = {RECOMB, Washington, DC (USA)},
pages = {90--99},
year = {2002},
month = {April},
publisher = {ACM Press},
url = {http://doi.acm.org/10.1145/565196.565208},
doi = {10.1145/565196.565208}
}
@article{PatternHunter02,
author = {Ma, Bin and Tromp, John and Li, Ming},
title = {{P}attern{H}unter: Faster and more sensitive homology search},
journal = {Bioinformatics},
year = {2002},
volume = {18},
number = {3},
pages = {440--445},
url = {http://bioinformatics.oxfordjournals.org/content/18/3/440},
pdf = {http://bioinformatics.oxfordjournals.org/content/18/3/440.full.pdf},
doi = {10.1093/bioinformatics/18.3.440}
}
@inproceedings{BurkhardtKarkkainenCPM01,
author = {Burkhardt, Stefan and K{\"a}rkk{\"a}inen, Juha},
title = {Better Filtering with Gapped q-Grams},
booktitle = {Proceedings of the 12th Symposium on Combinatorial Pattern Matching (CPM)},
pages = {73--85},
volume = {2089},
year = {2001},
series = {Lecture Notes in Computer Science},
publisher = {Springer},
month = {July},
url = {http://www.springerlink.com/content/gykw51mpjqnwrmqx},
pdf = {http://www.springerlink.com/content/gykw51mpjqnwrmqx/fulltext.pdf},
doi = {10.1007/3-540-48194-X_6}
}
@inproceedings{BuhlerTompaRECOMB01,
author = {Buhler, Jeremy and Tompa, Martin},
title = {Finding motifs using random projections},
booktitle = {Proceedings of the 5th Annual International Conference on Research in Computational Molecular Biology (RECOMB)},
pages = {69--76},
publisher = {ACM Press},
year = {2001},
url = {http://doi.acm.org/10.1145/369133.369172},
doi = {10.1145/369133.369172}
}
@article{LSHALLPAIRS01,
author = {Buhler, Jeremy},
title = {Efficient Large-Scale Sequence Comparison by Locality-Sensitive Hashing},
journal = {Bioinformatics},
year = {2001},
volume = {17},
number = {5},
pages = {419--428},
url = {http://bioinformatics.oxfordjournals.org/content/17/5/419},
pdf = {http://bioinformatics.oxfordjournals.org/content/17/5/419.full.pdf},
doi = {10.1093/bioinformatics/17.5.419}
}
@article{NicodemeSalvyFlajolet02TCS,
author = {Nicod{\`e}me, Pierre and Salvy, Bruno and Flajolet, Philippe},
title = {Motif statistics},
journal = {Theoretical Computer Science},
volume = {287},
number = {2},
year = {2002},
issn = {0304-3975},
pages = {593--617},
publisher = {Elsevier Science Publishers Ltd.},
url = {http://dx.doi.org/10.1016/S0304-3975(01)00264-X},
doi = {10.1016/S0304-3975(01)00264-X}
}
@inproceedings{FLASH93,
author = {Califano, Andrea and Rigoutsos, Isidore},
title = {Flash: A fast look-up algorithm for string homology},
booktitle = {Proceedings of the 1st International Conference on Intelligent Systems for Molecular Biology (ISMB)},
pages = {56--64},
year = {1993},
month = {July},
url = {http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=341106},
pdf = {http://www.aaai.org/Papers/ISMB/1993/ISMB93-007.pdf},
doi = {10.1109/CVPR.1993.341106}
}
This file was generated by bibtex2html 1.96. |