. Sf-altschul, . Tl-madden, . Schaffer, . Zhang, . Zhang et al., Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, Nucleic Acids Research, vol.25, issue.17, pp.3389-402, 1997.
DOI : 10.1093/nar/25.17.3389

S. E. Brenner, C. Chothia, and T. J. Hubbard, Assessing sequence comparison methods with reliable structurally identified distant evolutionary relationships, Proceedings of the National Academy of Sciences, vol.20, issue.9, pp.6073-6078, 1998.
DOI : 10.1016/S0968-0004(00)89080-5

C. Chothia, One thousand families for the molecular biologist, Nature, vol.357, issue.6379, pp.1317-1321, 2004.
DOI : 10.1038/357543a0

C. Orengo, J. Jones, and . Thornton, Protein superfamilles and domain superfolds, Nature, vol.372, issue.6507, pp.631-635, 1994.
DOI : 10.1038/372631a0

F. M. Pearl, C. F. Bennett, J. E. Bray, A. P. Harrison, N. Martin et al., The CATH database: an extended protein family resource for structural and functional genomics, Nucleic Acids Research, vol.31, issue.1, pp.452-455, 2003.
DOI : 10.1093/nar/gkg062

A. Andreeva, D. Howorth, S. E. Brenner, T. J. Hubbard, C. Chothia et al., SCOP database in 2004: refinements integrate structure and sequence family data, Nucleic Acids Research, vol.32, issue.90001, pp.226-229, 2004.
DOI : 10.1093/nar/gkh039

A. Marin, J. Pothier, K. Zimmermann, and J. Gibrat, FROST: A filter-based fold recognition method, Proteins: Structure, Function, and Genetics, vol.34, issue.4, pp.493-509, 2002.
DOI : 10.1002/prot.10231

R. H. Lathrop, The protein threading problem with sequence amino acid interaction preferences is NP-complete, "Protein Engineering, Design and Selection", vol.7, issue.9, pp.1059-1068, 1994.
DOI : 10.1093/protein/7.9.1059

R. H. Lathrop and T. F. Smith, Global Optimum Protein Threading with Gapped Alignment and Empirical Pair Score Functions, Journal of Molecular Biology, vol.255, issue.4, pp.641-665, 1996.
DOI : 10.1006/jmbi.1996.0053

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

N. Yanev and R. Andonov, Parallel divide and conquer approach for the protein threading problem, Concurrency and Computation: Practice and Experience, vol.16, issue.9, pp.961-974, 2004.
DOI : 10.1002/cpe.816

R. Andonov, S. Balev, and N. Yanev, Protein threading problem: From mathematical models to parallel implementations, INFORMS Journal on Computing Special Issue on Computational Molecular BiologyBioinformatics, vol.16, issue.4, pp.393-405, 2004.

J. Xu, M. Li, G. Lin, D. Kim, and Y. Xu, RAPTOR: OPTIMAL PROTEIN THREADING BY LINEAR PROGRAMMING, Journal of Bioinformatics and Computational Biology, vol.01, issue.01, pp.95-118, 2003.
DOI : 10.1142/S0219720003000186

Y. Xu and D. Xu, Protein threading using PROSPECT: Design and evaluation, Proteins: Structure, Function, and Genetics, vol.14, issue.3, pp.343-354, 2000.
DOI : 10.1002/1097-0134(20000815)40:3<343::AID-PROT10>3.0.CO;2-S

S. Balev, Solving the Protein Threading Problem by Lagrangian Relaxation, 4th International Workshop on Algorithms in Bioinformatics, pp.182-193, 2004.
DOI : 10.1007/978-3-540-30219-3_16

W. W. Li, R. W. Byrnes, J. Hayes, V. M. Reyes, A. Birnbaum et al., The encyclopedia of life project: Grid software and deployment. Special Issue on Grid Systems for Life Sciences, 2003.

T. Steinke, Alignment & threading on massively parallel computers, Genome Based Bioinformatics, 2003.

Y. Xu, D. Xu, and E. C. Uberbacher, An Efficient Computational Method for Globally Optimal Threading1, Journal of Computational Biology, vol.5, issue.3, pp.597-614, 1998.
DOI : 10.1089/cmb.1998.5.597

S. Altschul, Amino acid substitution matrices from an information theoretic perspective, Journal of Molecular Biology, vol.219, issue.3, pp.555-65, 1991.
DOI : 10.1016/0022-2836(91)90193-A

. Mo-dayhoff, B. Schwartz, and . Orcutt, Atlas of protein sequence and structure chapter A model of evolutionary change in proteins, National Biomedical Research Foundation, vol.5, pp.345-352, 1978.

S. Henikoff and J. Henikoff, Amino acid substitution matrices from protein blocks., Proceedings of the National Academy of Sciences, vol.89, issue.22, pp.10915-10924, 1992.
DOI : 10.1073/pnas.89.22.10915

URL : https://www.ncbi.nlm.nih.gov/pmc/articles/PMC50453/pdf

S. Needleman and C. Wunsch, A general method applicable to the search for similarities in the aminoacid sequence of two proteins, J Mol Biol, vol.48, 1970.

T. Smith and M. Waterman, Identification of common molecular subsequences, Journal of Molecular Biology, vol.147, issue.1, pp.195-202, 1981.
DOI : 10.1016/0022-2836(81)90087-5

W. Pearson, Flexible Sequence Similarity Searching with the FASTA3 Program Package, Methods Mol Biol, vol.132, pp.185-219, 2000.
DOI : 10.1385/1-59259-192-2:185

S. Brenner, C. Chothia, and T. Hubbard, Assessing sequence comparison methods with reliable structurally identified distant evolutionary relationships, Proceedings of the National Academy of Sciences, vol.20, issue.9, pp.6073-6081, 1998.
DOI : 10.1016/S0968-0004(00)89080-5

URL : http://www.ncbi.nlm.nih.gov/pmc/articles/PMC27587

T. Madej, S. Gibrat, and . Bryant, Threading a database of protein cores, Proteins: Structure, Function, and Genetics, vol.13, issue.3, pp.356-69, 1995.
DOI : 10.1002/prot.340230309

T. Akutsu and S. Miyano, On the approximation of protein threading, Theoretical Computer Science, vol.210, issue.2, pp.261-275, 1999.
DOI : 10.1016/S0304-3975(98)00089-9

N. Yanev and R. Andonov, Solving the protein threading problem in parallel, Proceedings International Parallel and Distributed Processing Symposium, pp.157-158, 2003.
DOI : 10.1109/IPDPS.2003.1213295

J. Xu, M. Li, G. Lin, D. Kim, and Y. Xu, Protein structure prediction by linear programming, Proceedings of The 7th Pacific Symposium on Biocomputing (PSB), pp.264-275, 2003.

G. Lancia, Integer programming models for computational biology problems, Journal of Computer Science and Technology, vol.7, issue.2, pp.60-77, 2004.
DOI : 10.1007/BF02944785

J. Blazewicz, P. Lukasiak, and M. Milostan, Some operations research methods for analyzing protein sequences and structures, 4OR, vol.4, issue.2, pp.91-123, 2006.
DOI : 10.1007/s10288-006-0089-y

S. Karlin, Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes., Proceedings of the National Academy of Sciences, vol.87, issue.6, pp.2264-2272, 1990.
DOI : 10.1073/pnas.87.6.2264

L. Mirny, E. Av-finkelstein, and . Shakhnovich, Statistical significance of protein structure prediction by threading, Proceedings of the National Academy of Sciences, vol.3, issue.3, pp.9978-83, 2000.
DOI : 10.1016/S1359-0278(98)00030-3

K. Zimmermann, A. Marin, J. Pothier, and J. Gibrat, Protein structure prediction: bioinformatic approach, chapter Protein threading statistics: an attempt to assess the significance of a fold assignment to a sequence, 2002.

J. Setubal and J. Meidanis, Introduction to computational molecular biology, PWS publishing company, 1997.

N. Yanev, P. Veber, R. Andonov, and S. Balev, Lagrangian approaches for a class of matching problems in computational biology, Computers and Mathematics with Applications, special issue on Computational Biology, 2006.
DOI : 10.1016/j.camwa.2006.12.103

URL : https://hal.archives-ouvertes.fr/inria-00335126

P. Veber, N. Yanev, R. Andonov, and V. Poirriez, Optimal Protein Threading by Cost-Splitting, WABI'05 (5th Workshop on Algorithms in Bioinformatics), pp.365-375, 2005.
DOI : 10.1007/11557067_30

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

V. Poirriez, R. Andonov, A. Marin, and J. Gibrat, FROST: Revisited and Distributed, 19th IEEE International Parallel and Distributed Processing Symposium, pp.200-201, 2005.
DOI : 10.1109/IPDPS.2005.231

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

R. Ihaka and R. Gentleman, R: A language for data analysis and graphics, Journal of Computational and Graphical Statistics, vol.5, issue.3, pp.299-314, 1996.

A. M. Lesk and G. D. Rose, Folding units in globular proteins., Proceedings of the National Academy of Sciences, vol.78, issue.7, pp.4304-4308, 1981.
DOI : 10.1073/pnas.78.7.4304

A. Bateman, L. Coin, R. Durbin, R. D. Finn, V. Hollich et al., The Pfam protein families database, Nucleic Acids Research, vol.32, issue.90001, pp.138-179, 2004.
DOI : 10.1093/nar/gkh121

URL : https://hal.archives-ouvertes.fr/hal-01294685

G. Collet, A. Marin, N. Yanev, R. Andonov, and J. Gibrat, Implementing a semi-global alignment algorithm for protein threading methods that use non-local score functions, Poster of the ROADEF conference, 2006.

G. Collet, N. Yanev, A. Marin, R. Andonov, and J. Gibrat, A flexible model for protein fold recognition, Septì emes Journes Ouvertes de Biologie, Informatique et Mathématiques (JOBIM), pp.215-216, 2006.
URL : https://hal.archives-ouvertes.fr/inria-00185460

I. Unité-de-recherche, I. Rennes, and I. , Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt : Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex (France) Unité de recherche, 2004.

I. De-voluceau-rocquencourt, BP 105 -78153 Le Chesnay Cedex (France) http://www.inria.fr ISSN, pp.249-6399