A path selection approach to global pairwise sequence alignment using integer linear optimizationFootnote†

†Dedicated to H. Th. Jongen on the occasion of his 60th birthday.

References

• Altschul , S , Gish , W and Miller , W . 1990 . Basic local alignment search tool . J. Mol. Biol. , 215 : 403 – 410 .
   PubMed Web of Science ®Google Scholar
• Altschul , SF , Madden , TL Schaffer , AA . 1997 . Gapped BLAST and PSI-BLAST: a new generation of protein database search programs . Nuc. Acids. Res. , 25 : 3389 – 3402 .
   PubMed Web of Science ®Google Scholar
• Dayhoff , M , Schwartz , R and Orcutt , B . 1978 . A model of evolutionary changes in proteins . Atlas Protein Sequences Structures , 5 : 345 – 352 .
   Google Scholar
• 2003 . Dash Optimization. Xpress-MP: Getting Started ,
   Google Scholar
• Floudas , CA . 1995 . Nonlinear and Mixed-integer Optimization: Fundamentals and Applications , New York : Oxford University Press .
   Google Scholar
• He , D and Arslan , AN . 2005 . A space-efficient algorithm for the constrained pairwise sequence alignment problem . Genome. Inform. , 16 : 237 – 246 .
   Google Scholar
• Henikoff , S and Henikoff , JG . 1992 . Amino acid substitution matrices from protein blocks . Proc. Natl. Acad. Sci. , 89 : 10915 – 10919 .
   PubMed Web of Science ®Google Scholar
• 2003 . ILOG CPLEX User's Manual 9.0 ,
   Google Scholar
• Krogh , A , Larsson , B von Heijne , G . 2001 . Predicting transmembrane protein topology with a hidden Markov model: application to complete genomes . J. Mol. Biol. , 305 : 567 – 580 .
   PubMed Web of Science ®Google Scholar
• Loose , C , Klepeis , JL and Floudas , CA . 2004 . A new pairwise folding potential based on improved decoy generation and side-chain packing . Prot. Struct. Funct. Bioinf. , 54 : 303 – 314 .
   PubMedGoogle Scholar
• McAllister , SR , Rajgaria , R and Floudas , CA . 2007 . “ A template-based mixed integer linear programming sequence alignment model ” . In Models and Algorithms for Global Optimization , Edited by: Törn , A. and Zilinskas , J. 343 – 360 . New York : Springer .
   Google Scholar
• McAllister , SR , Rajgaria , R and Floudas , CA . 2007 . Global pairwise sequence alignment through mixed integer linear programming: a template free approach . Optim. Method. Softw. , 22 : 127 – 144 .
   Web of Science ®Google Scholar
• Morgenstern , B , Dress , A and Werner , T . 1996 . Multiple DNA and protein sequence alignment based in segment-to-segment comparison . Proc. Natl. Acad. Sci. , 93 : 12098 – 12103 .
   PubMed Web of Science ®Google Scholar
• Needleman , SB and Wunsch , CD . 1970 . A general method applicable to the search for similarities in the amino acid sequence of two proteins . J. Mol. Biol. , 48 : 443 – 453 .
   PubMed Web of Science ®Google Scholar
• Notredame , C . 2002 . Recent progress in multiple sequence alignment: a survey . Pharmacogenomics , 3 : 131 – 144 .
   PubMedGoogle Scholar
• Pearson , WR and Lipman , DJ . 1988 . Improved tools for biological sequence comparison . Proc. Natl. Acad. Sci. , 85 : 2444 – 2448 .
   PubMed Web of Science ®Google Scholar
• Pearson , WR . 1990 . Rapid and sensitive sequence comparison with fastp and fasta . Methods Enzymol. , 183 : 63 – 98 .
   PubMed Web of Science ®Google Scholar
• Rajgaria , R , McAllister , SR and Floudas , CA . 2006 . A novel high resolution C-alpha C-alpha distance dependent force field based on a high quality decoy set . Prot. Struct. Funct. Bioinf. , 65 : 726 – 741 .
   PubMed Web of Science ®Google Scholar
• Smith , TF and Waterman , MS . 1981 . Identification of common molecular subsequences . J. Mol. Biol. , 147 : 195 – 197 .
   PubMed Web of Science ®Google Scholar
• Tang , CY , Lu , CL Chang , MD . 2003 . Constrained multiple sequence alignment tool development and its application to RNase family alignment . J. Bioinform. Comput. Biol. , 1 : 267 – 287 .
   Google Scholar
• Thompson , JD , Plewniak , F and Poch , O . 1999 . A comprehensive comparison of multiple sequence alignment programs . Nuc. Acids Res. , 27 : 2682 – 2690 .
   PubMed Web of Science ®Google Scholar
• Tobi , D and Elber , R . 2000 . Distance-dependent, pair potential for protein folding: results from linear optimization . Prot. Struct. Funct. Bioinf. , 41 : 40 – 46 .
   PubMed Web of Science ®Google Scholar
• Vingron , M . 1996 . Near-optimal sequence alignment . Curr. Opin. Struct. Biol. , 6 : 346 – 352 .
   Google Scholar
• Vinga , S and Almeida , J . 2003 . Alignment-free sequence comparison: a review . Bioinformatics , 19 : 513 – 523 .
   PubMed Web of Science ®Google Scholar