su_block_multiple_alignment.hpp
上传用户:yhdzpy8989
上传日期:2007-06-13
资源大小:13604k
文件大小:16k
源码类别:

生物技术

开发平台:

C/C++

  1. /*
  2.  * ===========================================================================
  3.  * PRODUCTION $Log: su_block_multiple_alignment.hpp,v $
  4.  * PRODUCTION Revision 1000.0  2004/06/01 18:14:33  gouriano
  5.  * PRODUCTION PRODUCTION: IMPORTED [GCC34_MSVC7] Dev-tree R1.7
  6.  * PRODUCTION
  7.  * ===========================================================================
  8.  */
  9. /*  $Id: su_block_multiple_alignment.hpp,v 1000.0 2004/06/01 18:14:33 gouriano Exp $
  10. * ===========================================================================
  11. *
  12. *                            PUBLIC DOMAIN NOTICE
  13. *               National Center for Biotechnology Information
  14. *
  15. *  This software/database is a "United States Government Work" under the
  16. *  terms of the United States Copyright Act.  It was written as part of
  17. *  the author's official duties as a United States Government employee and
  18. *  thus cannot be copyrighted.  This software/database is freely available
  19. *  to the public for use. The National Library of Medicine and the U.S.
  20. *  Government have not placed any restriction on its use or reproduction.
  21. *
  22. *  Although all reasonable efforts have been taken to ensure the accuracy
  23. *  and reliability of the software and data, the NLM and the U.S.
  24. *  Government do not and cannot warrant the performance or results that
  25. *  may be obtained by using this software or data. The NLM and the U.S.
  26. *  Government disclaim all warranties, express or implied, including
  27. *  warranties of performance, merchantability or fitness for any particular
  28. *  purpose.
  29. *
  30. *  Please cite the author in any work or product based on this material.
  31. *
  32. * ===========================================================================
  33. *
  34. * Authors:  Paul Thiessen
  35. *
  36. * File Description:
  37. *      Classes to hold alignment data
  38. *
  39. * ===========================================================================
  40. */
  41. #ifndef SU_BLOCK_MULTIPLE_ALIGNMENT__HPP
  42. #define SU_BLOCK_MULTIPLE_ALIGNMENT__HPP
  43. #include <corelib/ncbistl.hpp>
  44. #include <corelib/ncbiobj.hpp>
  45. #include <objects/seqalign/Seq_align.hpp>
  46. #include <list>
  47. #include <vector>
  48. #include <map>
  49. // forward declaration of BLAST_Matrix
  50. struct _blast_matrix;
  51. typedef struct _blast_matrix BLAST_Matrix_;
  52. BEGIN_SCOPE(struct_util)
  53. class Sequence;
  54. class Block;
  55. class UngappedAlignedBlock;
  56. class UnalignedBlock;
  57. class BlockMultipleAlignment : public ncbi::CObject
  58. {
  59. public:
  60.     enum {
  61.         eUndefined = kMax_UInt
  62.     };
  63.     typedef std::vector < const Sequence * > SequenceList;
  64.     BlockMultipleAlignment(const SequenceList& sequenceList);   // first sequence is master
  65.     ~BlockMultipleAlignment(void);
  66.     // add a new aligned block - will be "owned" and deallocated by BlockMultipleAlignment
  67.     bool AddAlignedBlockAtEnd(UngappedAlignedBlock *newBlock);
  68.     // these two should be called after all aligned blocks have been added; fills out
  69.     // unaligned blocks inbetween aligned blocks (and at ends). Also sets length.
  70.     bool AddUnalignedBlocks(void);
  71.     // Fills out the BlockMap for mapping alignment column -> block+column, special colors,
  72.     // and sets up conservation colors (although they're not calculated until needed).
  73.     bool UpdateBlockMap(bool clearRowInfo = true);
  74.     // find out if a residue is aligned, by row
  75.     bool IsAligned(unsigned int row, unsigned int seqIndex) const;
  76.     // stuff regarding master sequence
  77.     const Sequence * GetMaster(void) const { return m_sequences[0]; }
  78.     bool IsMaster(const Sequence *sequence) const { return (sequence == m_sequences[0]); }
  79.     // return sequence for given row
  80.     const Sequence * GetSequenceOfRow(unsigned int row) const
  81.     {
  82.         if (row < m_sequences.size())
  83.             return m_sequences[row];
  84.         else
  85.             return NULL;
  86.     }
  87.     // will be used to control padding of unaligned blocks
  88.     enum eUnalignedJustification {
  89.         eLeft,
  90.         eRight,
  91.         eCenter,
  92.         eSplit
  93.     };
  94.     // return alignment position of left side first aligned block (eUndefined if no aligned blocks)
  95.     unsigned int GetFirstAlignedBlockPosition(void) const;
  96.     // makes a new copy of itself
  97.     BlockMultipleAlignment * Clone(void) const;
  98.     // character query interface - "column" must be in alignment range [0 .. AlignmentWidth()-1]
  99.     bool GetCharacterAt(unsigned int alignmentColumn, unsigned int row,
  100.         eUnalignedJustification justification, char *character) const;
  101.     // get sequence and index (if any) at given position, and whether that residue is aligned
  102.     bool GetSequenceAndIndexAt(unsigned int alignmentColumn, unsigned int row,
  103.         eUnalignedJustification justification,
  104.         const Sequence **sequence, unsigned int *index, bool *isAligned) const;
  105.     // given row and sequence index, return alignment index; not the most efficient function - use sparingly
  106.     unsigned int GetAlignmentIndex(unsigned int row, unsigned int seqIndex, eUnalignedJustification justification);
  107.     // fill in a vector of UngappedAlignedBlocks
  108.     typedef std::vector < const UngappedAlignedBlock * > UngappedAlignedBlockList;
  109.     void GetUngappedAlignedBlocks(UngappedAlignedBlockList *blocks) const;
  110.     typedef std::vector < UngappedAlignedBlock * > ModifiableUngappedAlignedBlockList;
  111.     void GetModifiableUngappedAlignedBlocks(ModifiableUngappedAlignedBlockList *blocks);
  112.     // PSSM for this alignment (cached)
  113.     const BLAST_Matrix_ * GetPSSM(void) const;
  114.     void RemovePSSM(void) const;
  115.     // NULL if block before is aligned; if NULL passed, retrieves last block (if unaligned; else NULL)
  116.     const UnalignedBlock * GetUnalignedBlockBefore(const UngappedAlignedBlock *aBlock) const;
  117.     unsigned int NBlocks(void) const { return m_blocks.size(); }
  118.     unsigned int NAlignedBlocks(void) const;
  119.     unsigned int NRows(void) const { return m_sequences.size(); }
  120.     unsigned int AlignmentWidth(void) const { return m_totalWidth; }
  121.     // return a number from 1..n for aligned blocks, eUndefined for unaligned
  122.     unsigned int GetAlignedBlockNumber(unsigned int alignmentIndex) const
  123.         { return m_blockMap[alignmentIndex].alignedBlockNum; }
  124.     // for storing/querying info
  125.     double GetRowDouble(unsigned int row) const { return m_rowDoubles[row]; }
  126.     void SetRowDouble(unsigned int row, double value) const { m_rowDoubles[row] = value; }
  127.     const std::string& GetRowStatusLine(unsigned int row) const { return m_rowStrings[row]; }
  128.     void SetRowStatusLine(unsigned int row, const std::string& value) const { m_rowStrings[row] = value; }
  129.     // empties all rows' infos
  130.     void ClearRowInfo(void) const
  131.     {
  132.         for (unsigned int r=0; r<NRows(); ++r) {
  133.             m_rowDoubles[r] = 0.0;
  134.             m_rowStrings[r].erase();
  135.         }
  136.     }
  137.     ///// editing functions /////
  138.     // if in an aligned block, give block column and width of that position; otherwise eUndefined
  139.     void GetAlignedBlockPosition(unsigned int alignmentIndex,
  140.         unsigned int *blockColumn, unsigned int *blockWidth) const;
  141.     // get seqIndex of slave aligned to the given master seqIndex; eUndefined if master residue unaligned
  142.     unsigned int GetAlignedSlaveIndex(unsigned int masterSeqIndex, unsigned int slaveRow) const;
  143.     // returns true if any boundary shift actually occurred
  144.     bool MoveBlockBoundary(unsigned int columnFrom, unsigned int columnTo);
  145.     // splits a block such that alignmentIndex is the first column of the new block;
  146.     // returns false if no split occurred (e.g. if index is not inside aligned block)
  147.     bool SplitBlock(unsigned int alignmentIndex);
  148.     // merges all blocks that overlap specified range - assuming no unaligned blocks
  149.     // in that range. Returns true if any merge(s) occurred, false otherwise.
  150.     bool MergeBlocks(unsigned int fromAlignmentIndex, unsigned int toAlignmentIndex);
  151.     // creates a block, if given region of an unaligned block in which no gaps
  152.     // are present. Returns true if a block is created.
  153.     bool CreateBlock(unsigned int fromAlignmentIndex, unsigned int toAlignmentIndex,
  154.         eUnalignedJustification justification);
  155.     // deletes the block containing this index; returns true if deletion occurred.
  156.     bool DeleteBlock(unsigned int alignmentIndex);
  157.     // deletes all blocks; returns true if there were any blocks to delete
  158.     bool DeleteAllBlocks(void);
  159.     // shifts (horizontally) the residues in and immediately surrounding an
  160.     // aligned block; returns true if any shift occurs.
  161.     bool ShiftRow(unsigned int row, unsigned int fromAlignmentIndex, unsigned int toAlignmentIndex,
  162.         eUnalignedJustification justification);
  163.     // delete a row; returns true if successful
  164.     bool DeleteRow(unsigned int row);
  165.     // this function does two things: it extracts from a multiple alignment all slave rows listed for
  166.     // removal; and if pairwiseAlignments!=NULL, for each slave removed creates a new BlockMultipleAlignment
  167.     // that contains the alignment of just that slave with the master, as it was in the original multiple
  168.     // (i.e., not according to the corresponding pre-IBM MasterSlaveAlignment)
  169.     typedef std::list < BlockMultipleAlignment * > AlignmentList;
  170.     bool ExtractRows(const std::vector < unsigned int >& slavesToRemove, AlignmentList *pairwiseAlignments);
  171.     // merge in the contents of the given alignment (assuming same master, compatible block structure),
  172.     // addings its rows to the end of this alignment; returns true if merge successful. Does not change
  173.     // block structure - just adds the part of new alignment's aligned blocks that intersect with this
  174.     // object's aligned blocks
  175.     bool MergeAlignment(const BlockMultipleAlignment *newAlignment);
  176.     // reorder rows according to newOrder; returns true on success
  177.     bool ReorderRows(const std::vector < unsigned int >& newOrder);
  178. private:
  179.     SequenceList m_sequences;
  180.     typedef std::list < ncbi::CRef < Block > > BlockList;
  181.     BlockList m_blocks;
  182.     typedef struct {
  183.         Block *block;
  184.         unsigned int blockColumn, alignedBlockNum;
  185.     } BlockInfo;
  186.     typedef std::vector < BlockInfo > BlockMap;
  187.     BlockMap m_blockMap;
  188.     unsigned int m_totalWidth;
  189.     bool CheckAlignedBlock(const Block *newBlock) const;
  190.     UnalignedBlock * CreateNewUnalignedBlockBetween(const Block *left, const Block *right);
  191.     Block * GetBlockBefore(const Block *block);
  192.     Block * GetBlockAfter(const Block *block);
  193.     const Block * GetBlockBefore(const Block *block) const;
  194.     const Block * GetBlockAfter(const Block *block) const;
  195.     void InsertBlockBefore(Block *newBlock, const Block *insertAt);
  196.     void InsertBlockAfter(const Block *insertAt, Block *newBlock);
  197.     void RemoveBlock(Block *block);
  198.     // for cacheing of residue->block lookups
  199.     mutable unsigned int m_cachePrevRow;
  200.     mutable const Block *m_cachePrevBlock;
  201.     mutable BlockList::const_iterator m_cacheBlockIterator;
  202.     void InitCache(void);
  203.     // given a row and seqIndex, find block that contains that residue
  204.     const Block * GetBlock(unsigned int row, unsigned int seqIndex) const;
  205.     // intended for volatile storage of row-associated info (e.g. for alignment scores, etc.)
  206.     mutable std::vector < double > m_rowDoubles;
  207.     mutable std::vector < std::string > m_rowStrings;
  208.     // associated PSSM
  209.     mutable BLAST_Matrix_ *m_pssm;
  210. };
  211. // static function to create Seq-aligns out of multiple
  212. ncbi::objects::CSeq_align * CreatePairwiseSeqAlignFromMultipleRow(const BlockMultipleAlignment *multiple,
  213.     const BlockMultipleAlignment::UngappedAlignedBlockList& blocks, unsigned int slaveRow);
  214. // base class for Block - BlockMultipleAlignment is made up of a list of these
  215. class Block : public ncbi::CObject
  216. {
  217. public:
  218.     virtual ~Block(void) { }    // virtual destructor for base class
  219.     // makes a new copy of itself
  220.     virtual Block * Clone(const BlockMultipleAlignment *newMultiple) const = 0;
  221.     unsigned int m_width;
  222.     virtual bool IsAligned(void) const = 0;
  223.     // get sequence index for a column, which must be in block range (0 ... width-1)
  224.     virtual unsigned int GetIndexAt(unsigned int blockColumn, unsigned int row,
  225.         BlockMultipleAlignment::eUnalignedJustification justification) const = 0;
  226.     // delete a row
  227.     virtual void DeleteRow(unsigned int row) = 0;
  228.     virtual void DeleteRows(std::vector < bool >& removeRows, unsigned int nToRemove) = 0;
  229.     bool IsFrom(const BlockMultipleAlignment *alignment) const { return (alignment == m_parentAlignment); }
  230.     // given a row number (from 0 ... nSequences-1), give the sequence range covered by this block
  231.     typedef struct {
  232.         unsigned int from, to;
  233.     } Range;
  234.     const Range* GetRangeOfRow(int row) const { return &(m_ranges[row]); }
  235.     void SetRangeOfRow(unsigned int row, unsigned int from, unsigned int to)
  236.     {
  237.         m_ranges[row].from = from;
  238.         m_ranges[row].to = to;
  239.     }
  240.     // resize - add new (empty) rows at end
  241.     void AddRows(unsigned int nNewRows) { m_ranges.resize(m_ranges.size() + nNewRows); }
  242.     unsigned int NSequences(void) const { return m_ranges.size(); }
  243.     // reorder rows according to newOrder; returns true on success
  244.     bool ReorderRows(const std::vector < unsigned int >& newOrder);
  245. protected:
  246.     Block(const BlockMultipleAlignment *multiple) :
  247.         m_parentAlignment(multiple), m_ranges(multiple->NRows()) { }
  248.     const BlockMultipleAlignment *m_parentAlignment;
  249.     typedef std::vector < Range > RangeList;
  250.     RangeList m_ranges;
  251. };
  252. // a gapless aligned block; width must be >= 1
  253. class UngappedAlignedBlock : public Block
  254. {
  255. public:
  256.     UngappedAlignedBlock(const BlockMultipleAlignment *multiple) : Block(multiple) { }
  257.     bool IsAligned(void) const { return true; }
  258.     unsigned int GetIndexAt(unsigned int blockColumn, unsigned int row,
  259.         BlockMultipleAlignment::eUnalignedJustification justification =
  260.             BlockMultipleAlignment::eCenter) const  // justification ignored for aligned block
  261.         { return (GetRangeOfRow(row)->from + blockColumn); }
  262.     char GetCharacterAt(unsigned int blockColumn, unsigned int row) const;
  263.     void DeleteRow(unsigned int row);
  264.     void DeleteRows(std::vector < bool >& removeRows, unsigned int nToRemove);
  265.     Block * Clone(const BlockMultipleAlignment *newMultiple) const;
  266. };
  267. // an unaligned block; max width of block must be >=1. But range over any given
  268. // sequence can be length 0 (but not <0); if length 0, "to" is the residue before
  269. // the block, and "from" (= to+1) is the residue after.
  270. class UnalignedBlock : public Block
  271. {
  272. public:
  273.     UnalignedBlock(const BlockMultipleAlignment *multiple) : Block(multiple) { }
  274.     void Resize(void);  // recompute block width from current ranges
  275.     bool IsAligned(void) const { return false; }
  276.     unsigned int GetIndexAt(unsigned int blockColumn, unsigned int row,
  277.         BlockMultipleAlignment::eUnalignedJustification justification) const;
  278.     void DeleteRow(unsigned int row);
  279.     void DeleteRows(std::vector < bool >& removeRows, unsigned int nToRemove);
  280.     Block * Clone(const BlockMultipleAlignment *newMultiple) const;
  281. };
  282. END_SCOPE(struct_util)
  283. #endif // SU_BLOCK_MULTIPLE_ALIGNMENT__HPP
  284. /*
  285. * ---------------------------------------------------------------------------
  286. * $Log: su_block_multiple_alignment.hpp,v $
  287. * Revision 1000.0  2004/06/01 18:14:33  gouriano
  288. * PRODUCTION: IMPORTED [GCC34_MSVC7] Dev-tree R1.7
  289. *
  290. * Revision 1.7  2004/05/28 09:46:57  thiessen
  291. * restructure C-toolkit header usage ; move C Bioseq storage into su_sequence_set
  292. *
  293. * Revision 1.6  2004/05/27 21:34:08  thiessen
  294. * add PSSM calculation (requires C-toolkit)
  295. *
  296. * Revision 1.5  2004/05/26 14:49:59  thiessen
  297. * UNDEFINED -> eUndefined
  298. *
  299. * Revision 1.4  2004/05/26 14:30:16  thiessen
  300. * adjust handling of alingment data ; add row ordering
  301. *
  302. * Revision 1.3  2004/05/26 02:40:24  thiessen
  303. * progress towards LOO - all but PSSM and row ordering
  304. *
  305. * Revision 1.2  2004/05/25 16:12:30  thiessen
  306. * fix GCC warnings
  307. *
  308. * Revision 1.1  2004/05/25 15:52:18  thiessen
  309. * add BlockMultipleAlignment, IBM algorithm
  310. *
  311. */