{
  "id": "1705.06826",
  "version": "v1",
  "published": "2017-05-18T22:56:32.000Z",
  "updated": "2017-05-18T22:56:32.000Z",
  "title": "Simulations, Computations, and Statistics for Longest Common Subsequences",
  "authors": [
    "Qingqing Liu",
    "Christian Houdré"
  ],
  "comment": "12 pages, 10 figures",
  "categories": [
    "math.PR"
  ],
  "abstract": "The length of the longest common subsequences (LCSs) is often used as a similarity measurement to compare two (or more) random words. Below we study its statistical behavior in mean and variance using a Monte-Carlo approach from which we then develop a hypothesis testing method for sequences similarity. Finally, theoretical upper bounds are obtained for the Chv\\'atal-Sankoff constant of multiple sequences.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-05-18T22:56:32.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "65C05",
      "62F03",
      "60C05",
      "05A05"
    ],
    "keywords": [
      "longest common subsequences",
      "simulations",
      "statistics",
      "computations",
      "chvatal-sankoff constant"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}