# US 7,613,662 B2 · Apparatus, machine-readable medium, and system for the detection of atypical sequences via generalized compositional methods > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,613,662 B2 - Document ID: US7613662B2 - Status: Granted - Kind: B2 - Application number: 10/855,367 - Filed: 2004-05-28 - Published: 2005-12-01 - Granted: 2009-11-03 - Earliest claimed: 2004-05-28 - Assignees: International Business Machines Corporation - Inventors: Aristotelis Tsirigos; Isidore Rigoutsos - Web page: https://patentgrep.com/patent/US7613662B2 ## CPC - G16B 30/10: Sequence alignment; Homology search - G16B 30/00: ICT specially adapted for sequence analysis involving nucleotides or amino acids - Y10S 707/99936: Pattern matching access - G16B: BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY - Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein said template includes a number of characters that is less than nine. ### Claim 3 (depends on 2) The apparatus of claim 2, wherein said number lies in a range of six to eight. ### Claim 4 (depends on 1) The apparatus of claim 1, wherein said template optionally includes at least one “don't care” character. ### Claim 5 (depends on 1) The apparatus of claim 1, further comprising: a graphical user interface to allow a user to enter data for said template and to selectively view said information related to said number of occurrences; a typicality score calculator module to calculate a typicality score for a sequence fragment on a reference sequence based on said number of occurrences; and a threshold value calculator module to calculate an atypicality threshold for the sequence fragment under evaluation. ### Claim 6 (depends on 5) The apparatus of claim 5, further comprising: a lateral gene transfer (LGT) calculator to determine whether said typicality score for said sequence fragment is below said threshold. ### Claim 7 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. ### Claim 8 (depends on 7) The machine-readable storage medium of claim 7, wherein said template has a number of characters that is less than nine. ### Claim 9 (depends on 7) The machine-readable storage medium of claim 7, wherein said number lies in a range of six to eight. ### Claim 10 (depends on 7) The machine-readable storage medium of claim 7, wherein said template optionally includes at least one “don't care” character. ### Claim 11 (depends on 7) The machine-readable storage medium of claim 7, further comprising: a threshold value calculator module to calculate an atypicality threshold for said sequence fragment under evaluation. ### Claim 12 (depends on 11) The machine-readable storage medium of claim 11, further comprising: a lateral gene transfer (LGT) calculator module to determine whether said typicality score for said sequence fragment is below said threshold. ### Claim 13 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. ### Claim 14 (depends on 1) The apparatus of claim 1, wherein said number of occurrences of said template in said genetic sequence fragment under evaluation comprises a measure of whether said genetic sequence fragment under evaluation is native to an organism's genome or represents an atypicality acquired through a gene transfer from another organism. ### Claim 15 (depends on 5) The apparatus of claim 5, wherein said typicality score comprises a similarity metric. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein said similarity metric comprises one of: a correlation calculation; a χ2 test calculation; a Mahalanobis distance; and a relative entropy calculation.