Apparatus, machine-readable medium, and system for the detection of atypical sequences via generalized compositional methods
AssigneeInternational Business Machines Corporation
InventorsAristotelis Tsirigos, Isidore Rigoutsos
Life of this patent
Estimating the term…
Abstract
A method and system for determining whether a sequence fragment g is atypical with respect to a reference sequence G using compositional methods and including constructing a template from G and g respectively containing a sequence of characters for a comparison with one another, wherein a number of characters contained in the template exceeds two. For the case where the sequences at hand are genetic, the atypicality detection can be used to determine whether a given sequence fragment g is the result of a horizontal transfer event.
Claims16
An apparatus for determining that a sequence fragment is atypical with respect to a reference sequence, comprising:
- a compositional feature vector calculator to compute a number of occurrences of a given template having at least two template characters in a genetic sequence fragment under evaluation, said number of occurrences used to determine whether said genetic sequence fragment is atypical;
- a memory interface to retrieve said genetic sequence fragment under evaluation from a memory and to record said number of occurrences of said template in said genetic sequence fragment under evaluation;
- a processor to compare elements of said template sequentially with elements of said genetic sequence fragment under evaluation and to determine matches at each sequential position along said genetic sequence fragment under evaluation;
- and
- a display to selectively display information related to said number of occurrences,
- wherein an atypicality is determined based upon a similarity metric between said template and said genetic sequence fragment under evaluation.
A machine-readable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of determining that a sequence fragment is atypical with respect to a reference sequence in an organism, said program comprising:
- a compositional feature vector calculator to compute a number of occurrences of a given template having at least two template characters in a genetic fragment under evaluation;
- a memory interface module to retrieve said genetic fragment under evaluation from a memory and to record said number of occurrences of said template in said genetic fragment under evaluation;
- a typicality score calculator module to calculate a typicality score based on said number of occurrences;
- and
- a graphical user interface module to selectively permit a user to enter data for said template and to selectively display information related to said number of occurrences,
- wherein an atypicality is determined based upon a similarity metric between said template and said genetic sequence fragment under evaluation.
A system of determining that a sequence fragment g is atypical with respect to a reference sequence G, said system comprising:
- means for constructing at least one template, each said template containing a sequence of characters;
- means for counting a number of occurrences in said sequence g for each of said at least one template;
- means for counting a number of occurrences in said reference sequence G for each of said at least one template and determining whether said occurrence falls below a threshold that indicates atypicality;
- and
- means to selectively view information related to said number of occurrences,
- wherein a number of said characters contained in each of said at least one template exceeds two, and
- wherein an atypicality is determined based upon a similarity metric between said template and said genetic sequence fragment under evaluation.
Dependencies are inferred from the claim text.