libncbi6-dev 6.1.20120620-8 / usr / include / ncbi / alignmgr.h

/* ===========================================================================
*
*                            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:  alignmgr.h
*
* Author:  Sarah Wheelan
*
* Version Creation Date:   7/99
*
* $Revision: 6.72 $
*
* File Description: SeqAlign indexing and messaging functions 
*
* Modifications:
* --------------------------------------------------------------------------
* $Log: alignmgr.h,v $
* Revision 6.72  2001/07/10 11:12:27  wheelan
* added AlnMgrIndexIndexedChain
*
* Revision 6.71  2001/03/08 17:07:11  wheelan
* added AlnMgrGetParent and structure to support it
*
* Revision 6.70  2001/02/16 13:29:49  wheelan
* Added AMFreeAllIndexes
*
* Revision 6.69  2000/09/26 14:23:49  lewisg
* use AlnMgrSortbyID instead of AlnMgrSortSeqAligns
*
* Revision 6.68  2000/09/20 12:18:31  wheelan
* added new field to AM_msms structure
*
* Revision 6.67  2000/09/08 20:34:31  lewisg
* hacks to speed up bioseq to align coord computation
*
* Revision 6.66  2000/08/29 20:12:09  lewisg
* speed up color by alignment
*
* Revision 6.65  2000/08/28 16:18:21  sicotte
* moved AlnMgrSeqAlignMergeTwoPairwiseEx AlnMgrSeqAlignMergeTwoPairwise AlnMgrSeqAlignMergePairwiseSet to actutils.c
*
* Revision 6.64  2000/08/25 19:24:32  sicotte
* Add many functions to deal with merging alignment to go from pairwise sets to a single global (or local) alignment
*
* Revision 6.63  2000/08/18 14:20:51  lewisg
* add startsize field to AMAlignIndex so that lnMgrCopyIndexedParentIntoSap knows how big starts is
*
* Revision 6.62  2000/07/26 17:26:26  lewisg
* fix code for c++ inclusion
*
* Revision 6.61  2000/07/26 14:58:14  sicotte
* bug fixes to AlnMgrGetNextAlnBit. bug fix (overlapping fuzz) in AlnMgrMakeMultipleByScore, Added AlnMgrMakeMultipleByScoreExEx and AlnMgrRemoveInconsistentEx and AlnMgrDeleteHiddenEx to allow optional deletion of sealigns when converting indexes to seqaligns
*
* Revision 6.60  2000/07/25 18:55:54  sicotte
* Added AlnMgrDeleteHiddenEx and AlnMgrRemoveInconsistentFromPairwiseSetEx to make optional deleting of SeqAligns. Needed for Sequence Update
*
* Revision 6.59  2000/07/08 20:43:54  vakatov
* Get all "#include" out of the 'extern "C" { }' scope;  other cleanup...
*
* Revision 6.58  2000/06/01 14:17:55  wheelan
* added AlnMgrCheckOrdered and AlnMgrMakeRowsForOrdered
*
* Revision 6.57  2000/05/24 15:46:27  wheelan
* added AlnMgrRemoveInconsistentFromPairwiseSet and AlnMgrSortAlnSetByNthRowPos
*
* Revision 6.56  2000/05/16 17:14:38  wheelan
* added AlnMgrIsIBMable, AlnMgrIsEditable; made am_guess_numrows extern
*
* Revision 6.55  2000/05/09 14:23:01  wheelan
* added AlnMgrMakeMultipleByScoreEx
*
* Revision 6.54  2000/05/08 13:16:44  wheelan
* added AlnMgrGetNumAlnBlocks and AlnMgrGetNthBlockRange
*
* Revision 6.53  2000/05/05 11:53:53  wheelan
* added comment
*
* Revision 6.52  2000/05/03 19:30:59  wheelan
* added AM_NULL define
*
* Revision 6.51  2000/05/02 19:50:38  hurwitz
* fixed some bugs with launching DDE from DDV, added new alnMgr fn for positioning DDE on proper column
*
* Revision 6.50  2000/05/02 11:59:51  wheelan
* added SASeqDatFree
*
* Revision 6.49  2000/05/01 12:12:51  wheelan
* AlnMgrMapBioseqToSeqAlign now takes Int4 instead of Uint4
*
* Revision 6.48  2000/04/22 15:53:41  wheelan
* added AlnMgrIndexLite
*
* Revision 6.47  2000/04/10 19:33:27  wheelan
* added AlnMgrIsSAPNULL
*
* Revision 6.46  2000/04/05 17:41:47  wheelan
* added AlnMgrAddBlock and AlnMgrReplaceBlock
*
* Revision 6.45  2000/04/03 12:50:44  wheelan
* added AlnMgrGetSubAlignSpecial
*
* Revision 6.44  2000/03/17 14:25:25  wheelan
* changes to AlnMgrGetSubAlign
*
* Revision 6.43  2000/03/03 19:58:36  wheelan
* added AlnMgrDupTopNByScore
*
* Revision 6.42  2000/02/28 17:18:15  wheelan
* Added AlnMgrTossNeatRows for Cn3D
*
* Revision 6.41  2000/02/23 18:44:21  wheelan
* added AlnMgrNeatlyIndex for structure alignments
*
* Revision 6.40  2000/02/16 15:47:38  wheelan
* changed behavior of AlnMgrMakeMultByIntersectOnMaster
*
* Revision 6.39  2000/02/11 17:30:50  kans
* AlnMgrForcePairwiseContinuous moved to tools/actutils (SW)
*
* Revision 6.38  2000/02/09 20:22:25  wheelan
* added structure for AlnMgrDeleteNthRow
*
* Revision 6.37  2000/02/07 16:14:29  wheelan
* added AlnMgrTruncateSAP for structure-based indexing
*
* Revision 6.36  2000/02/02 14:37:30  wheelan
* added AlnMgrGetNthAlignedSegInNthRow and AlnMgrGetNthSegmentRange to make alignment editing easier
*
* Revision 6.35  2000/01/31 16:08:34  wheelan
* added unpacking functions, and AlnMgrMakeMultByIntersectOnMaster (does not work yet
*
* Revision 6.34  2000/01/29 14:02:12  wheelan
* added AlnMgrDeleteHidden and AlnMgrForcePairwiseContinuous
*
* Revision 6.33  2000/01/12 17:43:20  wheelan
* added AlnMgrGetNumSegments, AlnMgrDeleteRow
*
* Revision 6.32  1999/11/30 14:36:27  wheelan
* added AlnMgrMakeMultipleByScore
*
* Revision 6.31  1999/11/26 15:42:21  vakatov
* Fixed for the C++ and/or MSVC DLL compilation
*
* Revision 6.30  1999/11/18 19:30:24  wheelan
* added AlnMgrDeleteChildByPointer
*
* Revision 6.29  1999/10/25 18:16:44  wheelan
* Added AlnMgrGetUniqueSeqs
*
* Revision 6.28  1999/10/19 19:25:57  wheelan
* added is_aligned return to AlnMgrGetNextNthSeqRange; removed static functions; changed structures for AlnMgrMakeSegmentedMasterSlave
*
* Revision 6.27  1999/10/15 21:51:03  durand
* add AlnMgrIsSAPDiscAli()
*
* Revision 6.26  1999/10/15 15:41:20  wheelan
* fixed typo
*
* Revision 6.25  1999/10/15 15:15:05  wheelan
* added defines for AlnMgrGetNthRowTail
*
* Revision 6.24  1999/10/15 13:48:32  wheelan
* added AlnMgrGetNthRowTail
*
* Revision 6.23  1999/10/14 16:10:31  kans
* new includes and prototypes added
*
* Revision 6.22  1999/10/13 19:28:35  wheelan
* added speedup for segmented master-slave creation
*
* Revision 6.21  1999/10/07 13:37:33  wheelan
* added AlnMgrIndexSingleSeqAlign
*
* Revision 6.20  1999/10/06 19:34:49  wheelan
* added several viewer and editor management functions (AlnMgrCopy . . . )
*
* Revision 6.19  1999/10/05 15:15:18  wheelan
* added AlnMgrGetNthUnalignedForNthRow
*
* Revision 6.18  1999/10/04 14:58:17  wheelan
* added AlnMgrMapBioseqToSeqAlign
*
* Revision 6.17  1999/09/23 16:03:28  wheelan
* Added structures and functions to support segmented master-slave alignments
*
* Revision 6.16  1999/09/22 13:20:04  wheelan
* Added AlnMgrGetNextNthSeqRange and structures for segmented master-slave handling
*
* Revision 6.15  1999/09/21 19:14:15  wheelan
* added functions to make segmented master-slave, added fields to AlnMsg and AMAlignIndex structures
*
* Revision 6.14  1999/09/17 16:55:59  wheelan
* added AlnMgrPropagateSeqIdsBySapList
*
* Revision 6.13  1999/09/13 14:34:13  wheelan
* added more functions to support accessing the alignment by row number
*
* Revision 6.12  1999/09/06 16:37:36  wheelan
* added AlnMgrGetNextLengthBit and associated function
*
* Revision 6.11  1999/09/06 15:51:31  wheelan
* added row management functions, new structure for storing row information
*
* Revision 6.10  1999/09/01 20:12:18  wheelan
* added new merge function and the typedef for the structure it uses
*
* Revision 6.9  1999/09/01 14:38:46  wheelan
* added AlnMgrGetStrand
*
* Revision 6.8  1999/08/30 19:28:52  wheelan
* Added AlnMgrGetSapForSip for master-slave alignments
*
* Revision 6.7  1999/08/26 20:35:54  wheelan
* added parent indexing and pairwise-to-multiple functions
*
* Revision 6.6  1999/08/19 17:24:46  wheelan
* changed AMAlignIndex structure, added more api functions
*
* Revision 6.5  1999/08/12 20:56:57  vakatov
* [WIN32] Added missed LIBCALLBACK
*
* Revision 6.4  1999/08/12 12:41:56  wheelan
* added comments, and functions to index the parent
*
* Revision 6.3  1999/08/06 13:43:48  wheelan
* added several api functions; changed all names to AlnMgr..
*
* Revision 6.2  1999/07/30 14:08:41  wheelan
* added api functions to access indexes
*
* Revision 6.1  1999/07/29 12:56:45  wheelan
* initial checkin
*

* ==========================================================================
*/

#ifndef _ALIGNMGR_
#define _ALIGNMGR_

#include <ncbi.h>
#include <seqmgr.h>
#include <salutil.h>
#include <sequtil.h>
#include <salpedit.h>
#include <samutil.h>

#undef NLM_EXTERN
#ifdef NLM_IMPORT
#define NLM_EXTERN NLM_IMPORT
#else
#define NLM_EXTERN extern
#endif

#ifdef __cplusplus
extern "C" {
#endif

/* for SAIndex indextype field */
#define INDEX_SEGS 1
#define INDEX_PARENT 2

/* return values for AlnMgrCheckAlignForParent */
#define AM_CHILD 1
#define AM_PARENT 2

/* return values for AlnMgrCheckOverlapping and AlnMgrCheckOrdered */
#define AM_NOTORDERED -4
#define AM_ORDERED -3
#define CHECK_ERROR -2
#define NO_OVERLAP -1

/* values for amaip->mstype */
#define AM_MASTERSLAVE 1
#define AM_SEGMENTED_MASTERSLAVE 2
#define AM_NEATINDEX 3
#define AM_LITE 4
#define AM_NULL 5

/* values for AlnMgrGetNthRowTail */
#define LEFT_TAIL 1
#define RIGHT_TAIL 0

/* values for AlnMgrIsIBMable and AlnMgrIsEditable */
#define AM_ERROR        0
#define AM_NOIBM        1
#define AM_IBMCHANGE    2
#define AM_IBMNOCHANGE  3
#define AM_NOEDIT       4
#define AM_EDITGAPS     5
#define AM_EDITNOGAP    6

/***************************************************************************
*
*  Each child seqalign (segtype SAS_DENSEG) has an SAIndex structure, 
*  (in the sap->saip field -- the SAIndex is saip->indextype INDEX_SEGMENT
*  and may be accessed by casting the sap->saip pointer to an SAIndexPtr)
*  which records the alignment coordinates (each child must be a 
*  continuous alignment, so each will have obvious coordinates).  
*  The SAIndex structure has an array of SASeqDat structures, one 
*  for each "row" of the alignment, and each SASeqDat structure 
*  contains an array of Uint2s representing the segment numbers that 
*  the sequence in that row participates in (not gapped).
*
***************************************************************************/

typedef struct saseqdat {
   Uint2Ptr  sect;
   Uint2Ptr  unsect;
   Uint2     numsect;
   Uint2     numunsect;
} SASeqDat, PNTR SASeqDatPtr;

typedef struct saindex{
   Uint1 indextype;
   SeqAlignIndexFreeFunc freefunc;
   Uint4Ptr     aligncoords;
   Int4         master;
   SASeqDatPtr  PNTR ssdp;
   Int4         numseqs;
   SeqAlignPtr  parent;
} SAIndex, PNTR SAIndexPtr;

NLM_EXTERN SASeqDatPtr SASeqDatNew(void);
NLM_EXTERN void SASeqDatFree(SASeqDatPtr ssdp);
NLM_EXTERN SAIndexPtr SAIndexNew(void);
NLM_EXTERN Boolean SAIndexFree(VoidPtr index);

/***************************************************************************
*
*  Each parent seqalign (segtype SAS_DISC) has an AMAlignIndex structure
*  (in the sap->saip field -- the AMAlignIndex is saip->indextype 
*  INDEX_PARENT and may be accessed by casting the sap->saip pointer to
*  an AMAlignIndexPtr).  The AMAlignIndex has alignment coordinates across
*  all children, if possible, or across a subset of the children.  The
*  saps field is an array of SeqAlignPtrs, each of which appears in the 
*  order that it occurs in the combined alignment -- this means that a given
*  pointer may occur more than once.  The AMAlignDatPtr PNTR
*  points to an array of AMAlignDat structure, one per bioseq, each of
*  which has a sorted list of saps that the bioseq participates in.
*
***************************************************************************/
typedef struct row_source {
   SeqIdPtr    id;
   Uint4Ptr    which_saps;
   Uint4Ptr    num_in_sap;
   Uint4       numsaps;
   Uint1       strand;
   struct row_source PNTR next;
} RowSource, PNTR RowSourcePtr;

NLM_EXTERN RowSourcePtr RowSourceNew(void);
NLM_EXTERN RowSourcePtr RowSourceFree(RowSourcePtr rsp);

typedef struct amaligndat {
   SeqIdPtr    sip;
   SeqAlignPtr PNTR saps;
   Int4        numsaps;
   Uint2Ptr    segments;
   Uint2       numseg;
} AMAlignDat, PNTR AMAlignDatPtr;

typedef struct amalignindex {
   Uint1 indextype;
   SeqAlignIndexFreeFunc freefunc;
   Int2 mstype;
   Uint4Ptr aligncoords;
   SeqAlignPtr PNTR  saps;
   Uint4 numseg;
   Int4Ptr lens;
   Int4Ptr ulens;
   Int4Ptr starts;
   Int4 startsize;  /* length of the starts field in ints */
   Int4 alnsaps; /* the number of child seqaligns contained in the multiple */
   Int4 numsaps; /* the total number of child seqaligns */
   SeqIdPtr ids;
   Int4 numbsqs;
   RowSourcePtr PNTR rowsource;
   Uint4 numrows;
   Int4 master; /*tells which row is the master row*/
   AMAlignDatPtr PNTR amadp;
   SeqAlignPtr parent;
} AMAlignIndex, PNTR AMAlignIndexPtr;

NLM_EXTERN AMAlignIndexPtr AMAlignIndexNew(void);
NLM_EXTERN Boolean AMAlignIndexFree(VoidPtr index);
NLM_EXTERN AMAlignDatPtr AMAlignDatNew(void);
NLM_EXTERN AMAlignDatPtr AMAlignDatFree(AMAlignDatPtr amadp);

NLM_EXTERN void AMFreeAllIndexes(SeqAlignPtr sap);

/***************************************************************************
*
*  The AlnMsg structure is used by the function AlnMgrGetNextAlnBit.  The
*  calling function sets the fields which_master (NULL means alignment
*  coordinates), from_m, to_m (in alignment or master coordinates) and
*  either which_bsq or row_num (row_num avoids the repeated SeqId problem).  If
*  from_m and to_m are not set, the entire alignment is returned.  The function
*  fills in the AlnMsg structure and returns TRUE if there are more
*  segments of that bioseq in the region requested, FALSE if not. Be sure
*  not to set any other field -- many of these are used by the function
*  to indicate what has already been returned.  Also, make sure to call
*  AlnMsgNew instead of MemNew to allocate a new structure, as a couple of
*  fields must be initialized for the function to work correctly.
*
**************************************************************************/

typedef struct messagestruct {
/* set by function asking for alignment info */
   SeqIdPtr  which_master;
   Int4      from_m;
   Int4      to_m;
   SeqIdPtr  which_bsq;
   Int4      row_num;  /*  1-based numbering  */
/* ONLY set by AlnMgrGetNextAlnBit*/
   Int4      from_b;
   Int4      to_b;
   Uint1     gap;
   Uint1     strand;
   Int4      prev;
   Int4      real_from;
   Int4      prev_sap;
   Int4      len_left;
   Boolean   send_space;
   Uint2     place;
   Boolean   flag;
} AlnMsg, PNTR AlnMsgPtr;

NLM_EXTERN AlnMsgPtr AlnMsgNew(void);
NLM_EXTERN AlnMsgPtr AlnMsgFree(AlnMsgPtr amp);
NLM_EXTERN AlnMsgPtr AlnMsgReNew(AlnMsgPtr amp);

/* used by AlnMgrMakeMultSegments */
typedef struct am_tinyinfo {
   Int4   start;
   Int4   stop;
   Uint4  numgap;
   Uint2  which;
   Int4   numsap;
   struct am_tinyinfo PNTR next;
} AMTinyInfo, PNTR AMTinyInfoPtr;

typedef struct am_aligninfo {
   SeqAlignPtr  align;
   Int4 align_len;
} AMAlignInfo, PNTR AMAlignInfoPtr;

typedef struct am_alignkeeper {
   SeqAlignPtr  align;
   Boolean      am_delete;
} AMAlnKeeper, PNTR AMAlnKeeperPtr;


/* used by AlnMgrMakeSegmentedMasterSlave */
typedef struct am_msms {
   Int4         start;
   Int4         stop;
   Int4         sstart;
   Int4         sstop;
   Uint1        strand;
   SeqIdPtr     sip;
   SeqAlignPtr  sap;
   Int4         nsap;
   Int4         n;
   Int4         j;
   Int4         count;
   Int4         masternum;
   struct am_msms PNTR next;
} AMmsms, PNTR AMmsmsPtr;

typedef struct am_tinymsinfo {
   Int4       start;
   AMmsmsPtr  ams;
} AMTinyMSInfo, PNTR AMTinyMSInfoPtr;

typedef struct am_siplist {
   SeqIdPtr  sip;
   Int4      first_row;
   struct am_siplist PNTR next;
} AMsiplist, PNTR AMsiplistPtr;

typedef struct am_bittystruct {
   Int4  num1;
   Int4  num2;
   struct am_bittystruct PNTR next;
} AMBitty, PNTR AMBittyPtr;

NLM_EXTERN SeqAlignIndexPtr SeqAlignIndexNew(void);

/********************************************************************************
*
*  AlnMgrIndexSingleSeqAlign indexes (in place) only the first seqalign or
*  seqalign set in the chain that is passed in.  It will extensively
*  rearrange the first seqalign given.
*
********************************************************************************/
NLM_EXTERN Boolean AlnMgrIndexSingleSeqAlign(SeqAlignPtr sap);

NLM_EXTERN Boolean AlnMgrIndexSingleChildSeqAlign(SeqAlignPtr sap);

/********************************************************************************
*
*  AlnMgrReIndexSeqAlign frees the parent indexes, indexes any child
*  seqaligns that are not indexed (it assumes that any indexed child 
*  seqaligns are correctly indexed), and reindexes the set.
*
********************************************************************************/
NLM_EXTERN Boolean AlnMgrReIndexSeqAlign(SeqAlignPtr sap);

/***************************************************************************
*
*  AlnMgrIndexIndexedChain takes a linked list of indexed seqaligns and
*  indexes them as a set.
*
***************************************************************************/
NLM_EXTERN SeqAlignPtr AlnMgrIndexIndexedChain(SeqAlignPtr sap);

/********************************************************************************
*
*  AlnMgrIndexSeqAlign indexes (in place) the ENTIRE chain of seqaligns
*  and seqalign sets passed in, and extensively rearranges the seqalign.   
*
********************************************************************************/
NLM_EXTERN Boolean AlnMgrIndexSeqAlign(SeqAlignPtr sap);

/**********************************************************************
*
*  AlnMgrIndexLite disassembles the input alignment, indexes all child
*  alignments, and then puts them in the amaip->saps array.  It does
*  not attempt to create alignment coordinates across the whole set.
*  This is useful to keep sets of child alignments together (managing
*  BLAST hits, for example) when creating an overall alignment is
*  unnecessary.  This alignment can be freed normally, but many 
*  alignmgr functions will not work on the parent alignment (they 
*  will work on the child alignments).
*
**********************************************************************/
NLM_EXTERN Boolean AlnMgrIndexLite(SeqAlignPtr sap);

NLM_EXTERN SeqAlignPtr AlnMgrGetParent(SeqAlignPtr sap);

/***************************************************************************
*
*  AlnMgrUnpackSeqAlign rearranges any seqalign (except alignments with
*  more than two levels of nested discontinuous alignments) to a simple
*  discontinuous alignment or a linked list of alignments.
*
***************************************************************************/
NLM_EXTERN Boolean AlnMgrUnpackSeqAlign(SeqAlignPtr sap);


/***************************************************************************
*
*  AlnMgrRearrangeUnpacked transforms all child seqaligns into dense-seg
*  types, requiring some rearrangement for dense-diag sets.  This function
*  presumes that AlnMgrUnpackSeqAlign has already been called on the
*  alignment.
*
***************************************************************************/
NLM_EXTERN Boolean AlnMgrRearrangeUnpacked(SeqAlignPtr sap);


/***************************************************************************
*
*  AlnMgrAnythingToSeg takes any SeqAlign and does an in-place transformation
*  to the parent-child structure.  Each dense-seg, dense-diag and std-seg 
*  is put into its own seqalign, and the child seqaligns are linked 
*  together in no particular order and put in the sap->segs field of the
*  new parent (which takes over the pointer passed in).  The parent
*  has segtype SAS_DISC, and each child has segtype SAS_DENSEG or SAS_STD.
*  Each child, then, is a continuous, nonoverlapping alignment and therefore
*  may be indexed.
*
***************************************************************************/

NLM_EXTERN Boolean AlnMgrAnythingToSeg (SeqAlignPtr sap);

/***********************************************************************
*
*  AlnMgrIndexLinkedSegs and AlnMgrIndexParentSA create and fill in the
*  SASeqIndex and AMAlignIndex structures on the children and the parent,
*  respectively.  IndexLinkedSegs is called on the sap->segs field of
*  the parent, so that the pointer of the first child in the list
*  gets passed in.  AlnMgrIndexParentSA is called on the parent, and 
*  the children must already be indexed (the function does check) in order
*  for it to work.  AlnMgrIndexParentSA calls AlnMgrPropagateUpSeqIdPtrs
*  to create a list of all SeqIdPtrs present in all the children (each
*  is only listed once, in the order that its AMAlignDat structure occurs
*  in).
*
***********************************************************************/
NLM_EXTERN Boolean AlnMgrIndexLinkedSegs (SeqAlignPtr sap);
NLM_EXTERN Boolean AlnMgrIndexParentSA(SeqAlignPtr sap);
NLM_EXTERN SeqIdPtr AlnMgrPropagateUpSeqIdPtrs(SeqAlignPtr sap, Int4Ptr num);
NLM_EXTERN SeqIdPtr  AlnMgrPropagateSeqIdsBySapList(AMAlignIndexPtr amaip);
NLM_EXTERN SeqIdPtr  AlnMgrPropagateSeqIdsByRow(AMAlignIndexPtr amaip);

/***************************************************************************
*
*  AlnMgrRemoveInconsistentFromPairwiseSet is a greedy function to make
*  a consistent (nonoverlapping, linear) subset of alignments from a
*  set of pairwise alignments (often BLAST output, gapped or ungapped).
*  The input seqalign should either not be indexed or indexed using
*  AlnMgrIndexLite (just call it on the BLAST output).  fuzz specifies
*  how much overlap, if any, is allowed between alignments that are kept (for
*  example, if fuzz = 5, any alignments that overlap by 5 or less are
*  considered consistent).  If fuzz is less than 0, this will force spaces
*  between alignments (not sure why someone would want to do that, but
*  it is allowed).
*
*  The "Ex" version, also returns the rejected SeqAligns (in score order)
*     in 3 different lists according to the reason for rejection.
*
***************************************************************************/
NLM_EXTERN void AlnMgrRemoveInconsistentFromPairwiseSet(SeqAlignPtr sap, Int4 fuzz);
NLM_EXTERN void AlnMgrRemoveInconsistentFromPairwiseSetEx(SeqAlignPtr sap, Int4 fuzz, SeqAlignPtr PNTR wrong_strand, SeqAlignPtr PNTR overlaps_m,SeqAlignPtr PNTR overlaps_s);

NLM_EXTERN Boolean AlnMgrMakeMultipleByScore(SeqAlignPtr sap);
NLM_EXTERN Boolean AlnMgrMakeMultipleByScoreEx(SeqAlignPtr sap, Int4 fuzz);
NLM_EXTERN Boolean AlnMgrMakeMultipleByScoreExEx(SeqAlignPtr sap, Int4 fuzz,SeqAlignPtr PNTR wrong_strand, SeqAlignPtr PNTR overlaps_m,SeqAlignPtr PNTR overlaps_s);
NLM_EXTERN SeqAlignPtr AlnMgrDupTopNByScore(SeqAlignPtr sap, Int4 n);

/***************************************************************************
*
*  AlnMgrSortAlnSetByNthRowPos sorts a set of alignments so that they
*  are in (increasing) order along the specified row (to make sense, this
*  set of alignments should all have the same rows).
*
***************************************************************************/
NLM_EXTERN void AlnMgrSortAlnSetByNthRowPos(SeqAlignPtr sap, Int4 row);


/**********************************************************************
*
*  am_print_seqalign_indexes is a useful function for debugging; 
*  given a parent or child seqalign it prints a text summary of the
*  indexes for that seqalign.
*
***********************************************************************/
NLM_EXTERN void am_print_seqalign_indexes(SeqAlignPtr sap);


/**********************************************************************
*
*  AlnMgrCheckAlignForParent is called by almost every other function;
*  it checks whether the parents and children are correctly labeled
*  and indexed, and it returns AM_CHILD to indicate that the sap 
*  passed in is a child, AM_PARENT for a parent, or -1 for an error.
*  If the indexes aren't present, it will try to create them.
*
**********************************************************************/
NLM_EXTERN Int4 AlnMgrCheckAlignForParent(SeqAlignPtr sap);


/***********************************************************************
*
*  AlnMgrSortSeqAligns is a variant of the ValNodeSort function, and
*  calls very similar heapsort functions.  It can take a comparison
*  function that needs userdata, so more specific sorts are possible
*  without defining special structures for every type of sort.
*
***********************************************************************/
NLM_EXTERN SeqAlignPtr PNTR AlnMgrSortSeqAligns (SeqAlignPtr sap, int (LIBCALLBACK *compare)(VoidPtr, VoidPtr, VoidPtr), VoidPtr userdata, Int4Ptr numsap);
NLM_EXTERN SeqAlignPtr PNTR AlnMgrSortbyID (SeqAlignPtr sap, SeqId *sip, Int4Ptr numsap);

/**********************************************************************
*
*  AlnMgrCompareIncreasingBySeqIdPtr takes a SeqIdPtr as userdata,
*  and sorts the alignments in increasing order according to the 
*  region of the bioseq indicated that is contained in the alignment.
*  If the bioseq is not in the alignment, the alignment will be put
*  first, so all alignments in which the given bioseq does not 
*  participate occur at the beginning of the list, making it easy to
*  check for them and remove them.
*
**********************************************************************/
NLM_EXTERN int LIBCALLBACK AlnMgrCompareIncreasingBySeqIdPtr (VoidPtr base, VoidPtr large_son, VoidPtr userdata);

/*********************************************************************
*
*  AlnMgrFindFirst is crucial to the AlnMgrMakeFakeMultiple function;
*  it uses the sorted order of the seqaligns in each AMAlignDat
*  structure to guide a heapsort of all the seqaligns.
*
*********************************************************************/
NLM_EXTERN int LIBCALLBACK AlnMgrFindFirst(VoidPtr base, VoidPtr large_son, VoidPtr userdata);
NLM_EXTERN int LIBCALLBACK AlnMgrCompareTips(VoidPtr base, VoidPtr large_son);


/************************************************************************
*
*  AlnMgrGetNextLengthBit should be called iteratively on an alignment
*  to return the lengths of all the aligned and unaligned pieces in
*  the alignment.  Don't change the value in r, just pass in a pointer
*  to an allocated Int4 set to 0 initially.  The lengths of the unaligned
*  pieces are precomputed using AlnMgrGetMaxUnalignedLength; if no
*  precomputed values are found, this function is used to compute the
*  lengths on the fly.
*
************************************************************************/
NLM_EXTERN Boolean AlnMgrGetNextLengthBit(SeqAlignPtr sap, Int4Ptr length, Int4Ptr r);
NLM_EXTERN Int4 AlnMgrGetMaxUnalignedLength(SeqAlignPtr sap1, SeqAlignPtr sap2);


/*************************************************************************
*
*  AlnMgrGetNextAlnBit takes an AlnMsgPtr, with (at the minimum) the
*  which_bsq field filled in to indicate which bioseq should be returned.
*  The function returns the segments of the bioseq which span the region
*  of the alignment indicated, and can return them according to either
*  alignment coordinates (if which_master is NULL) or a master coordinate
*  system (need to fill in the SeqIdPtr of the master).  The function
*  returns TRUE if there are more segments of the bioseq to retrieve,
*  and FALSE if not.  It uses the two binary search functions to quickly
*  retrieve the required data from the indexes.
*
*************************************************************************/
NLM_EXTERN Boolean AlnMgrGetNextAlnBit(SeqAlignPtr sap, AlnMsgPtr amp);

/********************************************************************************
*
*  binary search functions
*
********************************************************************************/
NLM_EXTERN Uint4 binary_search_on_uint4_list(Uint4Ptr list, Uint4 pos, Uint4 listlen);
NLM_EXTERN Int4 binary_search_on_uint2_list(Uint2Ptr list, Uint2 ele, Uint2 listlen);
NLM_EXTERN Int4 binary_search_by_chunk(Int4Ptr list, Int4 ele, Int4 listlen, Int4 chunksize, Int4 offset);
NLM_EXTERN Int4 binary_search_segment_array(SASeqDatPtr ssdp, Int4 pos, Int4 numseq, Int4 offset, DenseSegPtr dsp);


/************************************************************************
*
*  These are several utility functions which get needed data from the
*  indexes.  "N" refers to row number (using a 1-based numbering system).
*
************************************************************************/
NLM_EXTERN Int4 AlnMgrGetAlnLength(SeqAlignPtr sap, Boolean fill_in);
NLM_EXTERN Int4 AlnMgrGetNumSeqs(SeqAlignPtr sap);
NLM_EXTERN SeqIdPtr AlnMgrGetUniqueSeqs(SeqAlignPtr sap, Int4Ptr n);
NLM_EXTERN SeqIdPtr AlnMgrGetNthSeqIdPtr(SeqAlignPtr sap, Int4 n);
NLM_EXTERN void AlnMgrGetNthSeqRangeInSA(SeqAlignPtr sap, Int4 n, Int4Ptr start, Int4Ptr stop);
NLM_EXTERN Int4 AlnMgrGetNumSegments(SeqAlignPtr sap);

/***************************************************************************
*
*  AlnMgrGetNumAlnBlocks returns the number of separate aligned regions
*  in the seqalign.  A return value of -1 indicates an error; a return
*  value of 0 indicates a NULL alignment (only one unaligned region and
*  no aligned regions.
*
***************************************************************************/
NLM_EXTERN Int4 AlnMgrGetNumAlnBlocks(SeqAlignPtr sap);
NLM_EXTERN Boolean AlnMgrGetNthBlockRange(SeqAlignPtr sap, Int4 n, Int4Ptr from, Int4Ptr to);


/***************************************************************************
*
*  AlnMgrGetNthAlignedSegInNthRow is similar to AlnMgrGetNextAlignBit,
*  but it takes an extra argument -- the number (1-based) of the segment
*  for which you want the alignment.  Fill in the AlnMsg structure as for
*  AlnMgrGetNextAlignBit, but leave out the from_m and to_m; and as usual,
*  don't modify the AlnMsg structure in between calls, and call AlnMsgReNew
*  for a new segment.  The from_b and to_b fields will work as in 
*  AlnMgrGetNextAlnBit -- if there is a gap, these are alignment coordinates;
*  otherwise they're sequence coordinates.
*
***************************************************************************/
NLM_EXTERN Boolean AlnMgrGetNthAlignedSegInNthRow(SeqAlignPtr sap, AlnMsgPtr amp, Int4 segnum);

NLM_EXTERN Boolean AlnMgrGetNthSegmentRange(SeqAlignPtr sap, Int4 n, Int4Ptr from, Int4Ptr to);

/********************************************************************************
*
*  AlnMgrGetNextNthSeqRange is called recursively to return the lengths of
*  all aligned and all internal unaligned regions of any row in a seqalign.
*  If there is an error, or if the function is called past the last block,
*  the function returns FALSE.  Set where to point to an allocated integer
*  equal to 0 on the first call and don't change it during the loop.  Set
*  the boolean unaligned to FALSE to get only the aligned regions, and TRUE to
*  get the aligned regions plus all internal unaligned regions.  For unaligned
*  regions, *is_aligned will be FALSE.
*
********************************************************************************/
NLM_EXTERN Boolean AlnMgrGetNextNthSeqRange(SeqAlignPtr sap, Int4 n, Int4Ptr start, Int4Ptr stop, Int4Ptr where, BoolPtr is_aligned, Boolean unaligned);


/********************************************************************************
*
*  AlnMgrGetNthRowTail retrieves the blocks of sequence on either end of the
*  alignment, by row.  which_tail is LEFT_TAIL to retrieve the ends which come
*  before alignment coordinate 0, and RIGHT_TAIL to retrieve the other ends.
*  The function returns TRUE if successful, FALSE for an error.
*
********************************************************************************/
NLM_EXTERN Boolean AlnMgrGetNthRowTail(SeqAlignPtr sap, Int4 n, Uint1 which_tail, Int4Ptr start, Int4Ptr stop, Uint1Ptr strand);
NLM_EXTERN Int4 AlnMgrGetMaxTailLength (SeqAlignPtr sap, Uint1 which_tail);
NLM_EXTERN Boolean AlnMgrGetNthUnalignedForNthRow(SeqAlignPtr sap, Int4 unaligned, Int4 row, Int4Ptr start, Int4Ptr stop);
NLM_EXTERN Uint1 AlnMgrGetStrand(SeqAlignPtr sap, SeqIdPtr sip);
NLM_EXTERN Uint1 AlnMgrGetNthStrand(SeqAlignPtr sap, Int4 n);
NLM_EXTERN Int4 AlnMgrGetNForSip(SeqAlignPtr sap, SeqIdPtr sip);
NLM_EXTERN Int4 AlnMgrGetNForSap(AMAlignIndexPtr amaip, SeqAlignPtr sap);

/********************************************************************************
*
*  AlnMgrGetAllNForSip is called in a while loop to return all the rows that a
*  seqid appears in in a given seqalign.  Use n = 0 to start, and then on
*  return, if the return is TRUE, n will be the row number of the next row
*  that the seqid appears in.  If the return is FALSE, either there was an
*  error or there are no (more) rows containing that seqid.
*
********************************************************************************/
NLM_EXTERN Boolean AlnMgrGetAllNForSip(SeqAlignPtr sap, SeqIdPtr sip, Int4Ptr n);

NLM_EXTERN Int4 AlnMgrGetSapForSip(AMAlignIndexPtr amaip, SeqIdPtr sip, Int4 which);
NLM_EXTERN Int4 AlnMgrMapToBsqCoords(SeqAlignPtr sap, Uint4 pos, SeqIdPtr sip, SeqIdPtr master); 

/********************************************************************************
*
*  AlnMgrMapRowCoords maps a position in a given row to the bioseq coordinate
*  of that row.  If master is NULL, the alignment is taken to be flattened;
*  otherwise it is an alignment according to that master (this will change the
*  correspondence between row coordinates and bioseq coordinates).  The return
*  value will be either a positive bioseq coordinate, or -1 if the bioseq is
*  gapped at that row position.
*
********************************************************************************/
NLM_EXTERN Int4 AlnMgrMapRowCoords(SeqAlignPtr sap, Uint4 pos, Int4 row, SeqIdPtr master);

/********************************************************************************
*
*  AlnMgrMapBioseqToSeqAlign takes a position in bioseq coordinates in a
*  row and maps it to seqalign coordinates, using the given master as
*  the alignment master (if master is NULL the alignment is flat).  A
*  return value of -1 indicates an error; a return value of -2 indicates
*  that the given bioseq coordinates are not contained in the alignment
*  specified.
*
********************************************************************************/
NLM_EXTERN Int4 AlnMgrMapBioseqToSeqAlign(SeqAlignPtr sap, Int4 pos, Int4 row_num, SeqIdPtr master);
NLM_EXTERN Int4 AlnMgrMapBioseqToSeqAlignEx(SeqAlignPtr sap, Int4 pos, Int4 row_num,
                                            SeqIdPtr master, Int4 *oldj);


/***********************************************************************
*
*  AlnMgrMakeFakeMultiple calls AlnMgrCheckOverlapping to decide whether
*  an alignment is linear.  Then, if possible, it calls AlnMgrMakeAlignCoords
*  to create alignment coordinates across all children contained in the
*  parent.
*
***********************************************************************/
NLM_EXTERN Boolean AlnMgrMakeFakeMultiple(SeqAlignPtr sap);

/**********************************************************************
*
*  AlnMgrNeatlyIndex is a very specialized function for structure
*  alignments and other alignments that have an implied row order.
*  It puts an index on the first seqalign in the set, and that index
*  only designates which seqaligns belong in which rows.  The input
*  alignments are not changed at all, and only the first alignment is
*  indexed.  This alignment cannot be displayed or accessed; it's only
*  a way to designate rows.
*
**********************************************************************/
NLM_EXTERN Boolean AlnMgrNeatlyIndex(SeqAlignPtr sap);

/**********************************************************************
*
*  AlnMgrTossNeatRows is called to create a subset of the NeatlyIndexed
*  alignment, only containing certain rows.  The array throwarray, of
*  length len, contains the (1-based) numbers of the rows to be left
*  out.  The function returns a duplicated alignment, which is not
*  yet indexed.  This function assumes a very strict row structure --
*  each row is represented by a single seqalign or seqalign set, and
*  the first row is the master.
*
**********************************************************************/
NLM_EXTERN SeqAlignPtr AlnMgrTossNeatRows(SeqAlignPtr sap, Int4Ptr throwarray, Int4 len);

/***************************************************************************
*
*   AlnMgrMakeMultByIntersectOnMaster is a specialized function that 
*   truncates the segments of segmented master-slave alignments to
*   force them to line up:
*
*   Master   XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
*   seq1        XXXXXXXX       XXXXXXXXXXXXXX
*   seq2       XXXXXXXXXX        XXXXXXX
*   seq3          XXXXXXXXXXXXXXXXXXXXXXX
*
*   becomes
*
*   Master        XXXXXX         XXXXXXX
*   seq1          XXXXXX         XXXXXXX
*   seq2          XXXXXX         XXXXXXX
*   seq3          XXXXXX         XXXXXXX
*
*   This indexing is different from the other type -- the input
*   alignments may actually be truncated, instead of just rearranged.
*   If allinblock is TRUE, then the function throws away any blocks that
*   have a missing sequence.
*
***************************************************************************/
NLM_EXTERN Boolean AlnMgrMakeMultByIntersectOnMaster(SeqAlignPtr sap, Boolean allinblock);
NLM_EXTERN Int4 am_guess_numrows(SeqAlignPtr sap);

/***************************************************************************
*
*   AlnMgrTruncateSAP truncates a given seqalign to contain only the
*   bioseq coordinates from start to stop on the indicated row.  Anything
*   before those coordinates is discarded; anything remaining afterwards
*   is made into another seqalign and put in sap->next (the original next,
*   if any, is now at sap->next->next). Doesn't work on parent seqaligns.
*   The function returns TRUE if the orignal alignment extended past stop.
*
***************************************************************************/
NLM_EXTERN Boolean AlnMgrTruncateSAP(SeqAlignPtr sap, Int4 start, Int4 stop, Int4 row);


NLM_EXTERN void AlnMgrMakeAlignCoords(SeqAlignPtr sap);
NLM_EXTERN Boolean AlnMgrMergeIntoMSMultByMaster(AMAlignIndexPtr amaip, Int4Ptr lens, Uint4Ptr numseg);
NLM_EXTERN Boolean AlnMgrMergeSegments(Int4Ptr lens, SeqAlignPtr sap, SeqIdPtr master, Int4Ptr where, Int4 which);
NLM_EXTERN Boolean AlnMgrFillInStarts(SeqAlignPtr PNTR saparray, Int4Ptr starts, Int4 numseg, Int4Ptr lens, Int4 numsaps, Uint4Ptr aligncoords);
NLM_EXTERN Int4 AlnMgrGetStartFromMaster(SeqAlignPtr sap, Int4 start);
NLM_EXTERN Uint4 AlnMgrGetMasterGapStartForSeg(SeqAlignPtr sap, Int4 which_gap, Uint4Ptr aligncoord);
NLM_EXTERN Boolean AlnMgrReconcileGaps(Int4Ptr lens, Uint4Ptr aligncoords, Int4 num);
NLM_EXTERN Boolean AlnMgrMakeMultSegments(AMAlignIndexPtr amaip);

NLM_EXTERN Int4 AlnMgrCheckOrdered(SeqAlignPtr sap);
NLM_EXTERN Int4 AlnMgrCheckOverlapping(SeqAlignPtr sap);

/******************************************************************************
*
*  AlnMgrGetMaxSegments simply adds up the number of segments for each
*  SeqAlign in a linked list, to get the maximum number of segments
*  for the merge of the list (for memory allocation in AlnMgrMakeFakeMultiple).
*
*******************************************************************************/
NLM_EXTERN Int4 AlnMgrGetMaxSegments(SeqAlignPtr sap);

/*******************************************************************************
*
*  Row Management functions:
*
*******************************************************************************/
NLM_EXTERN Int4 AlnMgrGetNumRows(SeqAlignPtr sap);
NLM_EXTERN Boolean AlnMgrMakeRowsForOrdered(SeqAlignPtr sap);
NLM_EXTERN Int4 AlnMgrGetMaxRowsForParentPartial(SeqAlignPtr sap);
NLM_EXTERN Boolean AlnMgrGetRowsForPartial(SeqAlignPtr sap);
NLM_EXTERN Boolean AlnMgrGetRowsForMasterSlave(SeqAlignPtr sap);


/*******************************************************************************
*
*  AlnMgrFindMaster returns the SeqIdPtr of the first bioseq present in all
*  child alignments, unless the sap->master field is set in the child alignments,
*  in which case that SeqIdPtr is returned (if it's the same in all children).
*
*******************************************************************************/
NLM_EXTERN SeqIdPtr AlnMgrFindMaster(SeqAlignPtr sap);

/*******************************************************************************
*
*  AlnMgrCheckRealMaster makes sure that the master seqid given appears
*  once and only once in each seqalign in the set if a parent is given,
*  or once and only one in the seqalign if a child is given.
*
*******************************************************************************/
NLM_EXTERN Boolean AlnMgrCheckRealMaster(SeqAlignPtr sap, SeqIdPtr master);

NLM_EXTERN Boolean AlnMgrMakeSegmentedMasterSlave(SeqAlignPtr sap);
NLM_EXTERN int LIBCALLBACK AlnMgrCompareAMS(VoidPtr base, VoidPtr large_son);
NLM_EXTERN int LIBCALLBACK AlnMgrCompareMasterAMS(VoidPtr base, VoidPtr large_son);

NLM_EXTERN Boolean AlnMgrForceMasterSlave(SeqAlignPtr sap);

NLM_EXTERN void AlnMgrSetMaster(SeqAlignPtr sap, SeqIdPtr master);
NLM_EXTERN void AlnMgrMakeMasterPlus(SeqAlignPtr sap);

/***************************************************************************
*
*  AlnMgrGetSubAlign returns a flattened multiple or pairwise alignment
*  corresponding to the indexed input alignment.  To get the entire
*  alignment, set from = 0 and to = -1.  (SUBALIGN)
*
***************************************************************************/
NLM_EXTERN SeqAlignPtr AlnMgrGetSubAlign(SeqAlignPtr sap, SeqIdPtr which_master, Int4 from, Int4 to);
NLM_EXTERN SeqAlignPtr AlnMgrGetSubAlignSpecial(SeqAlignPtr sap, Int4 master, Int4 from, Int4 to);

/********************************************************************************
*
*   viewer and editor management functions  
* 
********************************************************************************/ 

NLM_EXTERN SeqAlignPtr AlnMgrCopyIndexedParentSeqAlign(SeqAlignPtr sap);
NLM_EXTERN RowSourcePtr AlnMgrCopyRowSource(RowSourcePtr rsp);
NLM_EXTERN AMAlignDatPtr AlnMgrCopyamadp(AMAlignDatPtr amadp, SeqAlignPtr sap_tmp, SeqAlignPtr seg_head);
NLM_EXTERN SeqAlignIndexPtr AlnMgrCopyIndexesForChildSeqAlign(SeqAlignPtr sap);
NLM_EXTERN SASeqDatPtr  AlnMgrCopySASeqDat(SASeqDatPtr ssdp);
NLM_EXTERN SeqAlignPtr AlnMgrCopyAndIndexSingleAlignment(SeqAlignPtr sap);
NLM_EXTERN Boolean AlnMgrCopyIndexedParentIntoSap(SeqAlignPtr sap, SeqAlignPtr target);

/**********************************************************************
*
*  AlnMgrDeleteChildByPointer removes the specified child seqalign
*  from the set.  Note that this function does not reindex the seqalign;
*  the calling function must do that if the return is TRUE (use 
*  AlnMgrReIndexSeqAlign).
*
**********************************************************************/
NLM_EXTERN Boolean AlnMgrDeleteChildByPointer(SeqAlignPtr parent, SeqAlignPtr child);

/**********************************************************************
*
*  AlnMgrDeleteNthRow deletes the specified row from either a parent 
*  or a child seqalign.  Note that with a parent seqalign, this may
*  result in the deletion of a child seqalign.  The function does NOT
*  reindex the alignment; the calling function must do that upon a 
*  TRUE return (use AlnMgrReIndexSeqAlign).
*
**********************************************************************/
NLM_EXTERN Boolean AlnMgrDeleteNthRow(SeqAlignPtr sap, Int4 row);

/***************************************************************************
*  AlnMgrDeleteHiddenEx
*
*  Reads the Index, and updates the ->segs SeqAligns according
*  to the content of the index. If DeleteSalp then either 
*  Frees unused SeqAligns.. OR 
*  deletes them from the Object Manager.
*
*  AlnMgrDeleteHidden  calls the EX function with DeleteSalp=TRUE;
*  
****************************************************************************/

NLM_EXTERN void AlnMgrDeleteHidden(SeqAlignPtr sap, Boolean UseOM);
NLM_EXTERN void AlnMgrDeleteHiddenEx(SeqAlignPtr sap, Boolean UseOM, Boolean DeleteSalp);

/***************************************************************************
*
*  Both AlnMgrReplaceBlock and AlnMgrAddBlock require a flattened multiple
*  alignment plus a dense-seg structure (with the same number of rows
*  as the multiple alignment.  Discontinuous multiple alignments are fine,
*  and gapped alignments can also be edited; multiple pairwise alignments
*  cannot be edited (first call AlnMgrGetSubAlign to flatten the alignment,
*  or only edit one of the alignments in the set).  If the addition,
*  removal, or replacement of a block causes an unaligned region to
*  disappear, the functions will merge adjacent blocks to get rid of
*  unaligned regions of length 0.
*
***************************************************************************/
NLM_EXTERN Boolean AlnMgrReplaceBlock(SeqAlignPtr sap, DenseSegPtr new_block, Int4 block_num);
NLM_EXTERN Boolean AlnMgrAddBlock(SeqAlignPtr sap, DenseSegPtr new_block);

/********************************************************************************
*
*   SeqAlign types  
* 
********************************************************************************/ 
NLM_EXTERN  Boolean AlnMgrIsSAPDiscAli(SeqAlignPtr sap);

NLM_EXTERN Boolean AlnMgrIsSAPNULL(SeqAlignPtr sap);
NLM_EXTERN Int4 AlnMgrIsIBMable(SeqAlignPtr sap);
NLM_EXTERN Int4 AlnMgrIsEditable(SeqAlignPtr sap);


NLM_EXTERN Int4  AlnMgrMapBioseqToBioseq(SeqAlignPtr salp,Int4 pos,Int4 source_row,Int4 target_row,Boolean GetNextNonGap,Int4Ptr PostGap) ;

/*********************************************************************************
*
*   Pairwise to Global Alignment Functions: AlnMgrSeqAlignMergeTwoPairwise
*
*********************************************************************************/
NLM_EXTERN DenseSegPtr DenseDiagToGlobalDenseSeg(DenseDiagPtr ddp_head);
NLM_EXTERN DenseDiagPtr AlnMgrSeqAlignToDDP(SeqAlignPtr salp,Int4 aln_cut_from,Int4 aln_cut_to,Int4Ptr numseg_ptr);
NLM_EXTERN SeqAlignPtr AlnMgrMerge3OverlappingSeqAligns(SeqAlignPtr salp1,SeqAlignPtr salp_merging,SeqAlignPtr salp2,Int4 master_cut_pos1, Int4 master_cut_pos2);

#ifdef __cplusplus
}
#endif

#undef NLM_EXTERN
#ifdef NLM_EXPORT
#define NLM_EXTERN NLM_EXPORT
#else
#define NLM_EXTERN
#endif

#endif