View in EDS PDF Full Text

Counting Regular Expressions in Degenerated Sequences through Lazy Markov Chain Embedding.

Saved in:
Bibliographic Details
Title: Counting Regular Expressions in Degenerated Sequences through Lazy Markov Chain Embedding.
Authors: Nuel, G.1 gregory.nuel@parisdescartes.fr, Delos, V.1
Source: Annual International Conference on Computational Mathematics, Computational Geometry & Statistics. 2014, p100-108. 9p.
Subjects: Sequential machine theory, Cellular automata, Markov processes, Algorithm research, Embeddings (Mathematics)
Abstract: Nowadays, Next Generation Sequencing (NGS) produce huge number of reads which are combined using multiple alignment tech-niques to produce sequences. During this pro-cess, many sequencing errors are corrected, but the resulting sequences nevertheless contain a marginal level of uncertainty in the form of ~ 0.1% or less of degenerated positions (like the letter 'N' corresponding to any nucleotide). A previous work [7] showed that these degen-erated letters might lead to erroneous counts when performing pattern matching on these se-quences. An algorithm based on Determinis-tic Finite Automata (DFA) and Markov Chain Embedding (MCE) was suggested to deal with this problem. In this paper, we introduce a new version of this algorithm which uses Nondeterministic Fi-nite Automata (NFA) rather than DFA to per-form what we call "lazy MCE". This new ap-proach proves itself much faster than the previ-ous one and we illustrate its usefulness on two NGS datasets and a selection of regular expres-sions. A software implementing this al-gorithm is available: countmotif, http ://www.math-info.univ-paris5. [ABSTRACT FROM AUTHOR]
Copyright of Annual International Conference on Computational Mathematics, Computational Geometry & Statistics is the property of Global Science & Technology Forum and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 94854703
AccessLevel: 6
PubType: Conference
PubTypeId: conference
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Counting Regular Expressions in Degenerated Sequences through Lazy Markov Chain Embedding.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Nuel%2C+G%2E%22">Nuel, G.</searchLink><relatesTo>1</relatesTo><i> gregory.nuel@parisdescartes.fr</i><br /><searchLink fieldCode="AR" term="%22Delos%2C+V%2E%22">Delos, V.</searchLink><relatesTo>1</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Annual+International+Conference+on+Computational+Mathematics%2C+Computational+Geometry+%26+Statistics%22">Annual International Conference on Computational Mathematics, Computational Geometry & Statistics</searchLink>. 2014, p100-108. 9p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Sequential+machine+theory%22">Sequential machine theory</searchLink><br /><searchLink fieldCode="DE" term="%22Cellular+automata%22">Cellular automata</searchLink><br /><searchLink fieldCode="DE" term="%22Markov+processes%22">Markov processes</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithm+research%22">Algorithm research</searchLink><br /><searchLink fieldCode="DE" term="%22Embeddings+%28Mathematics%29%22">Embeddings (Mathematics)</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Nowadays, Next Generation Sequencing (NGS) produce huge number of reads which are combined using multiple alignment tech-niques to produce sequences. During this pro-cess, many sequencing errors are corrected, but the resulting sequences nevertheless contain a marginal level of uncertainty in the form of ~ 0.1% or less of degenerated positions (like the letter 'N' corresponding to any nucleotide). A previous work [7] showed that these degen-erated letters might lead to erroneous counts when performing pattern matching on these se-quences. An algorithm based on Determinis-tic Finite Automata (DFA) and Markov Chain Embedding (MCE) was suggested to deal with this problem. In this paper, we introduce a new version of this algorithm which uses Nondeterministic Fi-nite Automata (NFA) rather than DFA to per-form what we call "lazy MCE". This new ap-proach proves itself much faster than the previ-ous one and we illustrate its usefulness on two NGS datasets and a selection of regular expres-sions. A software implementing this al-gorithm is available: countmotif, http ://www.math-info.univ-paris5. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Annual International Conference on Computational Mathematics, Computational Geometry & Statistics is the property of Global Science & Technology Forum and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=94854703
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.5176/2251-1911_CMCGS14.28
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 9
        StartPage: 100
    Subjects:
      – SubjectFull: Sequential machine theory
        Type: general
      – SubjectFull: Cellular automata
        Type: general
      – SubjectFull: Markov processes
        Type: general
      – SubjectFull: Algorithm research
        Type: general
      – SubjectFull: Embeddings (Mathematics)
        Type: general
    Titles:
      – TitleFull: Counting Regular Expressions in Degenerated Sequences through Lazy Markov Chain Embedding.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Nuel, G.
      – PersonEntity:
          Name:
            NameFull: Delos, V.
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: 2014
              Type: published
              Y: 2014
          Identifiers:
            – Type: issn-print
              Value: 22511911
          Titles:
            – TitleFull: Annual International Conference on Computational Mathematics, Computational Geometry & Statistics
              Type: main
ResultId 1