/* =========================================================================== * * PUBLIC DOMAIN NOTICE * National Center for Biotechnology Information (NCBI) * * This software/database is a "United States Government Work" under the * terms of the United States Copyright Act. It was written as part of * the author's official duties as a United States Government employee and * thus cannot be copyrighted. This software/database is freely available * to the public for use. The National Library of Medicine and the U.S. * Government do not place any restriction on its use or reproduction. * We would, however, appreciate having the NCBI and the author cited in * any work or product based on this material. * * Although all reasonable efforts have been taken to ensure the accuracy * and reliability of the software and data, the NLM and the U.S. * Government do not and cannot warrant the performance or results that * may be obtained by using this software or data. The NLM and the U.S. * Government disclaim all warranties, express or implied, including * warranties of performance, merchantability or fitness for any particular * purpose. * * =========================================================================== * * File Name: spidey.h * * Author: Sarah Wheelan * * Version Creation Date: 5/01 * * $Revision: 6.11 $ * * File Description: mrna-to-genomic alignment algorithms and functions * * Modifications: * -------------------------------------------------------------------------- * $Log: spidey.h,v $ * Revision 6.11 2001/12/18 18:00:18 wheelan * add strand * * Revision 6.10 2001/11/20 12:13:28 wheelan * made SPI_GetProteinFrommRNA EXTERN * * Revision 6.9 2001/11/05 16:14:53 wheelan * added option to print multiple alignment to a file * * Revision 6.8 2001/10/04 12:34:07 wheelan * added bigintron option * * Revision 6.7 2001/10/03 14:19:29 wheelan * include new alignment manager * * Revision 6.6 2001/09/04 13:46:37 wheelan * made SPI_RemoveInconsistentAlnsFromSet and SPI_flip_sa_list extern * * Revision 6.5 2001/08/24 13:44:35 wheelan * changed printaln to Int4 * * Revision 6.4 2001/08/06 16:49:25 wheelan * changed revcompthresh parameter to 55 from 65 * * Revision 6.3 2001/07/11 17:57:07 wheelan * added typedefs for multiple alignments * * Revision 6.2 2001/07/10 16:44:42 wheelan * added functions to make a multiple alignment * * Revision 6.1 2001/05/24 16:27:58 wheelan * initial checkin * * * ========================================================================== */ #ifndef _SPIDEY_ #define _SPIDEY_ #include #include #include #include #undef NLM_EXTERN #ifdef NLM_IMPORT #define NLM_EXTERN NLM_IMPORT #else #define NLM_EXTERN extern #endif #ifdef __cplusplus extern "C" { #endif #define SPI_DROPOFF 50 #define SPI_GAPOPEN 10 #define SPI_GAPEXTEND 3 #define SPI_PENALTY -5 #define SPI_SPLICETHRESH 0.0001 #define SPI_MAXGAP 4 /* maximum gap allowed in SPI_ExtendAlnAlg */ #define SPI_REVCOMPTHRESH 55 /* minimum allowed % of splice sites present */ /* If model is < minimum, then the reverse */ /* complement will be checked. */ #define SPI_COVERDIFF 15 /* amount the %coverage is allowed to drop in the */ /* reverse complement models */ #define SPI_MISMTCHDIFF 10 /* amount the %mismatch is allowed to rise in */ /* the reverse complement models */ #define SPI_TEENYEXON 6 /* smallest exon to look for */ #define SPI_ENDFUZZ 13 /* if the overall alignment misses less than or equal */ /* to this amount on the ends of the mRNA, the */ /* alignment will be extended. */ #define SPI_MINBLASTSIZE 7 /* smallest bit that can go into BlastTwoSequencesByLoc */ #define SPI_MINPOLYASIZE 5 /* minimum #A's to call a poly(A)+ tail */ #define SPI_MAXPOLYASIZE 200 /* maximum number of nucleotides to bother */ /* scanning for a tail */ #define SPI_LINKERSIZE 8 /* maximum number of non-A's to allow on end of tail */ #define SPI_INTRONSIZE 35000 /* used only to decide whether an mRNA may have fallen */ /* off a contig */ #define SPI_INTRONSIZEXL 120000 /* if spot->bigintron TRUE, use this */ #define SPI_BIGINTRON 100000 /* max size of 1st and last introns, if 1st and last exons */ /* have to be found by SPI_FindPiece. */ #define SPI_BIGINTRONXL 240000 /* if spot->bigintron TRUE, use this */ #define SPI_PADDING 0 /* how much each region is padded on each side */ #define SPI_NUMSITES 4 /* number of alternative splice sites to consider per exon */ #define SPI_BIGOVERLAP 12 /* above this cutoff, the overlap won't be doubled */ /* to get the window in which to search for splice sites */ #define SPI_EXONMERGESIZE 15 /* exons closer than this to each other will get merged */ #define SPI_FLUFF 16 /* amount to search on either side of splice site for interspecies comp. */ #define SPI_UNKNOWN 0 #define SPI_CONSISTENT 1 #define SPI_IMPOSSIBLE 2 #define SPI_DONE1 3 #define SPI_DONE2 4 #define SPI_FUZZ 20 /* amount of overlap/underlap allowed to consider hits consistent*/ #define SPI_LEFT 0 #define SPI_RIGHT 1 #define SPI_BOTH 2 #define SPI_NEITHER 3 #define SPI_REVERSEUNKNOWN 0 #define SPI_REVERSE 1 #define SPI_NOTREVERSED 2 #define SPI_MULT 1 #define SPI_NOTMULT 2 #define SPI_LINE 60 /* line length for text alignment output -- must be more than SPI_PSPLICE */ #define SPI_PSPLICE 10 /* length of genomic sequence to print before and after each exon */ #define SPI_SPACER 12 /* space at the beginning of each printed alignment line */ #define SPI_NUMCOLS 8 /* number of columns in the tab-delimited file of position info for draft */ /* defines for organisms (determines which splice matrices to use) */ #define SPI_VERTEBRATE 1 #define SPI_FLY 2 #define SPI_PLANT 3 #define SPI_CELEGANS 4 /* return codes for progress callback */ #define SPI_START 1 #define SPI_PROGRESS 2 #define SPI_FINISHED 3 typedef struct spi_bsinfo { BioseqPtr bsp; SeqLocPtr lcaseloc; struct spi_bsinfo PNTR next; } SPI_bsinfo, PNTR SPI_bsinfoPtr; typedef struct spi_alninfo { FloatHi bit_score; SeqAlignPtr sap; Int2 used; } SPI_AlnInfo, PNTR SPI_AlnInfoPtr; typedef struct spi_ival { Int4 n; SeqAlignPtr sap; Int4 gstart; Int4 gstop; Int4 mstart; Int4 mstop; Uint2 strand; Int2 used; Int4 score; struct spi_ival PNTR next; } SPI_Ival, PNTR SPI_IvalPtr; typedef struct spiexonprof { Int4 exonnum; Int4Ptr mismatches; Int4 nummismatches; struct spiexonprof PNTR next; } SPI_ExonProf, PNTR SPI_ExonProfPtr; typedef struct spi_mrna { Uint1 strand; Boolean revcomp; Int4 numexons; FloatHiPtr exonid; /* percent identity per exon */ Int4Ptr exongaps; /* number of gaps in each exon alignment */ Uint1Ptr splicedon; /* for each exon, is splice donor site (right) present? */ Uint1Ptr spliceacc; /* for each exon, is splice acceptor site (left) present? */ Uint1 missingends; /* SPI_LEFT, SPI_RIGHT, SPI_BOTH, or SPI_NEITHER */ Int4Ptr mstarts; /* exon starts, in mRNA coordinates */ Int4Ptr mstops; /* exon stops, in mRNA coordinates */ Int4Ptr gstarts; /* exon starts, in genomic coordinates */ Int4Ptr gstops; /* exon stops, in genomic coordinates */ SeqAlignPtr PNTR saps; /*indexed alignments for exons */ Int4 mRNAcoverage; /* percentage of the mRNA contained in this alignment */ FloatHi mismatch; /* percent mismatches in entire alignment */ Int4 polyAtail; /* if +, length of polyA tail that doesn't align */ /* if negative, length of polyAtail that does align */ Boolean fallsoff; /* does this mRNA fall of the end of the contig? */ SeqAlignPtr parent; /* parent of exon alignment set */ SeqAlignPtr continuous; /* continuous alignment over whole gene */ SPI_ExonProfPtr epp; /* positions of mismatches (for printing) */ CharPtr protein; /* sequence of the protein translated from the mRNA */ Int4 transstart; /* translation start position */ Boolean holes; /* are there holes in the mRNA alignment? */ struct spi_mrna PNTR next; } SPI_mRNA, PNTR SPI_mRNAPtr; typedef struct spi_utrinfo { FloatHi left; FloatHi right; } SPI_UTRInfo, PNTR SPI_UTRInfoPtr; typedef struct spi_seq { CharPtr seq; Int4 start; } SPI_Seq, PNTR SPI_SeqPtr; typedef struct spi_mult { SeqAlignPtr PNTR exons; Int4 numexons; } SPI_Mult, PNTR SPI_MultPtr; typedef struct spi_reginfo { Boolean revcomp; Int4 gstart; Int4 gstop; Int4 mstart; Int4 mstop; Uint1 strand; SPI_mRNAPtr smp; Int4 coverage; Int4 score; Int4 polyAtail; /* length of polyA(+) tail that doesn't align */ Boolean fallsoff; /* this mRNA may fall off the end of the genomic sequence */ SPI_UTRInfo utr; /* if this is a CDS, UTR %ids are here */ SPI_MultPtr smu; struct spi_reginfo PNTR next; } SPI_RegionInfo, PNTR SPI_RegionInfoPtr; typedef struct spi_tinyinfo { Int4 start; Int4 n; struct spi_tinyinfo PNTR next; } SPI_TinyInfo, PNTR SPI_TinyInfoPtr; typedef struct spi_pos { Int4 lgroup; Int4 group; Int4 order; } SPI_Pos, PNTR SPI_PosPtr; typedef struct spi_fragmentptr { Int4 start; Int4 stop; Int4 fragnum; /* original fragment number, for reference */ SeqLocPtr slp; SPI_PosPtr position_orig; /* the position info (if any) given for this fragment */ Int4 position_mrna; /* after alignment to mRNA, where is this fragment */ Int4 reverse; /* is this fragment reversed with respect to the mRNA */ SeqAlignPtr sap; /* indexed parent of the alignments for this fragment to the mRNA */ SPI_mRNAPtr smp; /* info for the alignment to this fragment */ Uint1 donor; /* does this (set of) alignment(s) have a donor site to the next frag? */ Uint1 acceptor; /* acceptor site ? */ struct spi_fragmentptr PNTR next; } SPI_Frag, PNTR SPI_FragPtr; typedef struct spi_fragherd { Int4 polyAtail; /* length of polyAtail on the mRNA */ Int4 numfrags; SPI_FragPtr PNTR sfparray; } SPI_FragHerd, PNTR SPI_FragHerdPtr; typedef struct spi_fraginfo { Int4 mrnastart; Int4 mrnastop; Uint1 strand; Int4 sfpnum; Int4 fragnum; SPI_PosPtr position_orig; } SPI_FragInfo, PNTR SPI_FragInfoPtr; typedef struct spi_mRNAtoherd { BioseqPtr bsp_mrna; /* mrna sequence */ Int4 numpieces; Int4 numexons; Int4Ptr exons; /* array which specifies which pieces go with which exons */ Int4Ptr fragments; /* array of fragment numbers, one per piece */ Int4Ptr sfpnum; /* array of sfp numbers, one for each piece */ Uint1Ptr fallsoff; /* for each piece, does it fall off fragment? */ Uint1Ptr strands; /* genomic strand, one per piece */ Int4Ptr mstarts; /* mrna starts, one per piece */ Int4Ptr mstops; /* mrna stops, one per piece */ Int4Ptr gstarts; /* genomic starts, one per piece */ Int4Ptr gstops; /* genomic stops, one per piece */ Int4Ptr lens; /* length of alignment for each piece */ Int4Ptr pmismatch; /* number of mismatches per piece */ Int4Ptr pgaps; /* number of gaps in alignment for each piece */ FloatHiPtr exonid; /* percent identity per exon */ Int4Ptr exongaps; /* number of gaps per exon */ Uint1Ptr splicedon; /* for each piece, is splice donor site (right) present? */ Uint1Ptr spliceacc; /* for each piece, is splice acceptor site (left) present? */ Uint1 missingends; /* SPI_LEFT, SPI_RIGHT, SPI_BOTH, or SPI_NEITHER */ SeqAlignPtr PNTR saps; /* indexed alignments, one for each piece (not exon) */ FloatHi mRNAcoverage; /* percentage of the mRNA contained in this alignment */ Boolean gaps; /* are there internal pieces missing from the mRNA alignment? */ FloatHi mismatch; /* percent mismatches in entire alignment */ SPI_ExonProfPtr epp; struct spi_mRNAtoherd PNTR next; } SPI_mRNAToHerd, PNTR SPI_mRNAToHerdPtr; typedef struct spi_exonherdinfo { Int4 fragmentnum; SeqAlignPtr sap; Uint1 donor; Uint1 acceptor; Int4 sfpnum; struct spi_exonherdinfo PNTR next; } SPI_ExonHerdInfo, PNTR SPI_ExonHerdInfoPtr; typedef struct spi_splice { Int4 i; FloatHi score; FloatHi score2; Int4 diff; } SPI_Splice, PNTR SPI_SplicePtr; typedef struct spi_fragsplice { SPI_SplicePtr splarray; Int4 spllen; Int4 boundary; } SPI_FragSpl, PNTR SPI_FragSplPtr; typedef struct spi_progress { Int4 percentdone; Int4 returncode; } SPI_Progress, PNTR SPI_ProgressPtr; typedef Boolean (LIBCALLBACK *SPI_ProgressCallback)(SPI_ProgressPtr progress); typedef struct spi_options { FloatHi firstpasseval; FloatHi secpasseval; FloatHi thirdpasseval; Int4 organism; Int4 numreturns; Int4 idcutoff; Int4 lencutoff; Int4 printaln; Boolean interspecies; Boolean printasn; SeqAlignPtr PNTR sap_head; CharPtr draftfile; SeqLocPtr lcaseloc; Boolean fetchcds; Boolean printheader; Boolean ace; SPI_ProgressCallback callback; Int4 from; /* to restrict genomic interval */ Int4 to; /* " */ Boolean makemult; /* make a multiple alignment from numerous returns? */ Boolean bigintron; Uint1 strand; /* to restrict the search to one genomic strand */ } SPI_Options, PNTR SPI_OptionsPtr; typedef struct spi_n { Int4 n1; Int4 n2; Int4 n3; Int4 n4; Int4 n5; Int4 n6; } SPI_n, PNTR SPI_nPtr; typedef struct spi_block { SeqAlignPtr sap; Int4 from_g; Int4 to_g; struct spi_block PNTR next; } SPI_Block, PNTR SPI_BlockPtr; NLM_EXTERN SPI_RegionInfoPtr SPI_AlnSinglemRNAToGen(SPI_bsinfoPtr spig, SPI_bsinfoPtr spim, FILE *ofp, FILE *ofp2, SPI_OptionsPtr spot); NLM_EXTERN SPI_mRNAToHerdPtr SPI_AlnSinglemRNAToPieces(SPI_bsinfoPtr spig_head, SPI_bsinfoPtr spim, FILE *ofp, FILE *ofp2, SPI_OptionsPtr spot); NLM_EXTERN void SPI_MakeMultipleAlignment(SPI_RegionInfoPtr srip_head); NLM_EXTERN void SPI_PrintMultipleAlignment(SPI_RegionInfoPtr srip, Boolean html, BioseqPtr bsp, FILE * ofp); NLM_EXTERN void SPI_RegionListFree (SPI_RegionInfoPtr srip); /************************************************************************************* * * SPI_AlnmRNAToGenomic is available to outside programs; just pass in the two * bioseqs and options (to use default options, just pass in NULL, and to use * other options, call SPI_OptionsNew to get an initialized options pointer and * make the desired changes). If options are passed in, they should be freed * using SPI_OptionsFree. SPI_AlignmRNAToGenomic returns a linked list of * SPI_mRNAPtrs, one per gene model (default is to only return one gene model). * Each SPI_mRNAPtr (see above) has arrays specifying the exon boundaries in * genomic and mRNA coordinates as well as information about splice sites, * percent identity, number of gaps, etc. The SPI_mRNAPtr also has one alignment * per exon as well as a single alignment (smp->continuous) that covers the entire * gene, with big gaps in the mRNA for the genomic introns. The SPI_mRNAPtr should * be freed by the calling function, using SPI_mRNAFree. * * SPI_AlnmRNAToGenomic should only be used on finished sequence; it can handle * interspecies comparisons but doesn't work on draft sequence. * *************************************************************************************/ NLM_EXTERN SPI_mRNAPtr SPI_AlignmRNAToGenomic(BioseqPtr bsp_genomic, BioseqPtr bsp_mrna, SPI_OptionsPtr spot); /*************************************************************************** * * SPI_flip_sa_list takes the head of a list of seqaligns and switches * the first and second row of every alignment (alignments should all have * two rows). Then, the indexes are freed and the alignments are reindexed. * ***************************************************************************/ NLM_EXTERN void SPI_flip_sa_list (SeqAlignPtr sap); /*************************************************************************** * * SPI_RemoveInconsistentAlnsFromSet is a greedy algorithm that first * sorts the alignments by score, then takes the highest-scoring * alignment and compares it to the next-highest-scoring alignment, which * is deleted if it is contained; on subsequent loops each next-highest- * scoring alignment is compared to the set of alignments that have * been kept. The alignments can be sorted along the first or * second sequence; the alignments will be reversed so that they are * all on the plus strand of the sequence to be examined. * The input alignment must be indexed at least at the LITE level; * conflicting child alignments will be deleted, not hidden, by this * function. This function assumes that all children have the same two * rows. The 'compact' parameter tells the function whether to try to * keep alignments that are more to the left in genomic coordinates, or * more to the right. * ***************************************************************************/ NLM_EXTERN void SPI_RemoveInconsistentAlnsFromSet(SeqAlignPtr sap, Int4 fuzz, Int4 n, Int4 compact); NLM_EXTERN void SPI_bsinfoFreeList (SPI_bsinfoPtr spi); NLM_EXTERN void SPI_mRNAFree (SPI_mRNAPtr smp); NLM_EXTERN SPI_OptionsPtr SPI_OptionsNew(void); NLM_EXTERN void SPI_OptionsFree (SPI_OptionsPtr spot); NLM_EXTERN void SPI_is_donor (Uint1Ptr sequence, Int4 seqlen, FloatHiPtr score, Int4 org); NLM_EXTERN void SPI_is_acceptor (Uint1Ptr sequence, Int4 seqlen, FloatHiPtr score, Int4 org); /*************************************************************************** * * SPI_GetProteinFrommRNA takes an mRNA bioseq and returns a string * which is the best protein translation of the mRNA. First, the function * looks to see whether there are any annotated CDSs, and if so, it uses * the translation of the annotated CDS. If not, the function translates * the mRNA in all 3 reading frames and looks for the frame with the * longest protein, then returns that protein. * ***************************************************************************/ NLM_EXTERN CharPtr SPI_GetProteinFrommRNA(BioseqPtr bsp_mrna, Int4Ptr start); #ifdef __cplusplus } #endif #undef NLM_EXTERN #ifdef NLM_EXPORT #define NLM_EXTERN NLM_EXPORT #else #define NLM_EXTERN #endif #endif