APPLICATION-SPECIFIC ARRAY PROCESSORS FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM OF THREE SEQUENCES Footnote∗

∗ This work was partially supported by Pole de Modeiisation de la region Picardie

Footnote†

†A preliminary version of this paper appeared in [30]

References

• Aho , A. , Hirschberg , D.S. and Ullman , J.D. Bounds on the complexity of the longest common subsequence problem . J. ACM 23 ( 1 ) ( 1976 ), 1 – 12 .
   Web of Science ®Google Scholar
• Allison , L. A fust algorithm for the optimal alignment of three strings . J. Theor. Biol. 164 ( 2 ) ( 1993 ), 261 – 269 .
   PubMed Web of Science ®Google Scholar
• Allison , L. Dix , T.I. A bit string longest common subsequence algorithm . Inform. Process. Letters 23 ( 1986 ), 305 – 310 .
   Web of Science ®Google Scholar
• Apostolico , A. , Browne , S. and Guerra , C. Fast linear-space computations of longest common subsequences . Theoret. Comput. Sci. 92 ( 1992 ), 3 – 17 .
   Web of Science ®Google Scholar
• Chan , S.C. , Chiu , D.K.Y. and Wong , K.C. A survey of multiple sequence comparison methods . Bull. Math. Biol. 54 ( 4 ) ( 1992 ), 563 – 598 .
   PubMed Web of Science ®Google Scholar
• Chang , J.H. , Ibarra , O.H. and Pallis , MA. Parallel parsing on a one-way array of finite-state machines . IEEE Trans. Comp. C-36 ( 1987 ), 64 – 75 .
   Web of Science ®Google Scholar
• Cheng , H.D. and Fu , K.S. VLSI architectures for string matching and pattern matching . Pattern Recogn. 20 ( 1 ) ( 1987 ), 125 – 141 .
   Web of Science ®Google Scholar
• Chin , F. and Poon , C.K. Performance analysis of some simple heuristics for computing longest common subsequences . Algorithmica 12 ( 1994 ), 293 – 311 .
   Web of Science ®Google Scholar
• Chin , F.Y.L. and Poon , C.K. A fast algorithm for computing longest common subsequences of small alphabet size . J. Inform. Process. 13 ( 4 ) ( 1990 ), 463 – 469 .
   Google Scholar
• Dančcilc , V. and Paterson , M.S. Longest common subsequences . Proc. Ilth Annual Symposium on Theoretical Aspects of Computer Science . Academic Press , Springer-Verlag , LNCS 775 ( 1994 ), 127 – 142 .
   Google Scholar
• Gotoh , O. , Optimal alignment between groups of sequences and its application to multiple sequence alignment . Comput. Applic. Biosci. 9 ( 3 ) ( 1993 ), 361 – 370 .
   PubMedGoogle Scholar
• Gotoh , O. Alignment of three biological sequences with an efficient traceback procedure . J. Theor. Biol. 121 ( 1986 ), 327 – 337 .
   PubMed Web of Science ®Google Scholar
• Griggs , J. , Halton , P. , Odiyzko , A. and Waterman , M.S. On the number of alignments of k sequences . Graphs Combinal. 6 ( 1990 ), 133 – 146 .
   Web of Science ®Google Scholar
• Hakata , K. and Imai , H. The longest common subsequence problem for small alphabet size between many strings . Proc. 3rd International Symposium on Algorithms and Computations. Academic Press , Springer-Verlag . LNCS 650 ( 1992 ), 469 – 478 .
   Google Scholar
• Hall , P.A.V. and Dowling , G.R. Approximate string matching . Comput. Surveys 12 ( 4 ) ( 1980 ), 381 – 402 .
   Web of Science ®Google Scholar
• Hirschberg , D.S. An information-theoretic lower bound for the longest common subsequence problem . Inform. Process. Letters 7 ( 1 ) ( 1978 ), 40 – 41 .
   Web of Science ®Google Scholar
• Hirschberg , D.S. Algorithms for the longest common subsequence problem . J. ACM 24 ( 4 ) ( 1977 ), 664 – 675 .
   Web of Science ®Google Scholar
• Hirschberg , D.S. A linear space algorithm for computing maximal common subsequences . Comm. ACM 18 ( 6 ) ( 1975 ), 341 – 343 .
   Web of Science ®Google Scholar
• Hsu , W. and Du , M. New algorithms for the longest common subsequence problem . J. Comput. Syst. Sci. 29 ( 1984 ), 133 – 152 .
   Web of Science ®Google Scholar
• Hsu , W. and Du , M. Computing a longest common subsequence for a set of strings . BIT 20 ( 5 ) ( 1984 ), 350 – 353 .
   Google Scholar
• Hunt , J.W. , Szymanski , T. G. A fast algorithm for computing longest common subsequences . Comm. ACM 20 ( 1977 ). 350 – 353 .
   Web of Science ®Google Scholar
• Ibarra , O.H. , Jiang , T. and Wang , T. String editing on a one-way linear array of finite-state machines . IEEE Trans. Comp. 41 ( 1 ) ( 1992 ), 112 – 118 .
   Web of Science ®Google Scholar
• Irving , R.W. and Fraser , C.B. Two algorithms for the longest common subsequence of three (or more) strings . Proc. 3rd Annual Symposium on Combinatorial Pattern Matching . Academic Press , Springer-Verlag , LNCS 664 ( 1992 ), 214 – 229 .
   Google Scholar
• Itoga , S.Y. The string merging problem. BIT 21 ( 1981 ), 20 – 30 .
   Web of Science ®Google Scholar
• Kumar , S.K. and Rangan , C.P. A linear space algorithm for the longest common subsequence problem . Acta Inform. 24 ( 1987 ), 353 – 362 .
   Google Scholar
• Kung , H.T. Why systolic architectures? IEEE Comput. 15 ( 1 ) ( 1980 ), 37 – 46 .
   Google Scholar
• Kung , H.T. and Lam , M.S. Wafer-scale integration and two-level pipelined implementation of systolic arrays . J. Parall. Distrib. Comput. 1 ( 1984 ), 32 – 63 .
   Web of Science ®Google Scholar
• Lin , Y.C. New systolic arrays for the longest common subsequence problem . Parallel Comput. 20 ( 1994 ), 1323 – 1334 .
   Web of Science ®Google Scholar
• Luce , G. and Myoupo , J.F. Array processor algorithms for the longest common subsequence problem of three strings . Tech. Report LaRIA96–09,. Université de Picardie Jules Verne . Amiens . France .
   Google Scholar
• Luce. G. and Myoupo , J.F. Efficient parallel computing of a longest common subsequence of three strings . Proc. 8th SI AM Conf. on Parallel Processing for Scientific Computing . Minneapolis , MN , 1997 .
   Google Scholar
• Maier , D. The complexity of some problems on subsequences and supersequences . J. ACM 25 ( 2 ) ( 1978 ), 322 – 336 .
   Web of Science ®Google Scholar
• Manber , U. , Miller , W. , Myers , G. and Wu , S. An O(NP) sequence comparison algorithm . Inform. Process. Letters 35 ( 1990 ), 317 – 323 .
   Web of Science ®Google Scholar
• Masek , W.J. and Paterson , M.S. A faster algorithm for computing string edit distances . J. Compui. Syst. Sci. 20 ( 1980 ), 18 – 31 .
   Web of Science ®Google Scholar
• Mukbopadhyay , A. A fast algorithm for the longest-common-subsequence problem . Inform. Sci. 20 ( 1980 ), 69 – 82 .
   Web of Science ®Google Scholar
• Nakatsu , N. , Kambayashi , Y. and Yajima , S. A longest common subsequence algorithm suitable for similar text string . Acta Inform. 18 ( 1982 ), 171 – 179 .
   Web of Science ®Google Scholar
• Pcvzner , P.A. and Waterman , M.S. Matrix longest common subsequence problem, duality and Hilberl bases . Proc. 3rd Annual Symposium on Combinatorial Pattern Matching . Academic Press , Springer-Verlag , LNCS 664 ( 1992 ), 79 – 89 .
   Google Scholar
• Rick , C. A new flexible algorithm for the longest common subsequence problem . Proc. 6th Annual Symposium on Combinatorial Pattern Matching . Academic Press , Springer-Verlag , LNCS 937 ( 1995 ), 340 – 351 .
   Google Scholar
• Robert , Y. Tchuente M. , A systolic array for the longest common subsequence problem . Inform. Process. Letters 21 ( 1985 ), 191 – 198 .
   Web of Science ®Google Scholar
• Sankoff , D. and Kruskal , J.B. Time warps, string edits, and macromolecules the theory and practice of sequence comparison . Addison-Wesley , Reading , MA , 1983 .
   Google Scholar
• Ukkonen , E. Algorithm for approximate string matching . Inform, and Control 64 ( 1985 ), 100 – 118 .
   Google Scholar
• Wagner , R.A. and Fischer , M.J. The string-to-string correction problem . J. ACM 21 ( 1 ) ( 1974 ), 168 – 173 .
   Web of Science ®Google Scholar
• Wong , C.K. and Chandra , A.K. Bounds for the string editing problem . J. ACM 23 ( 1 ) ( 1976 ), 13 – 16 .
   Web of Science ®Google Scholar
• ∗ This work was partially supported by Pole de Modeiisation de la region Picardie
   Google Scholar
• †A preliminary version of this paper appeared in [30]
   Google Scholar
• Dagger;Corresponding author. Faculte de Mathematiques et dTnformatique, Universite de Picardie Jules Verne, 33 rue Saint-Leu 80039, Amiens Cedex 01, France. E-mail: {luce, myoupo}@laria.u-picardie.fr.
   Google Scholar