/usr/include/seqan/chaining/tree_chain.h is in seqan-dev 1.3-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 | // ==========================================================================
// SeqAn - The Library for Sequence Analysis
// ==========================================================================
// Copyright (c) 2006-2010, Knut Reinert, FU Berlin
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// * Neither the name of Knut Reinert or the FU Berlin nor the names of
// its contributors may be used to endorse or promote products derived
// from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
// DAMAGE.
//
// ==========================================================================
#ifndef SEQAN_HEADER_TREECHAIN_H
#define SEQAN_HEADER_TREECHAIN_H
#include <algorithm>
#include <vector>
namespace seqan{
// compute chain spec for G0 and G1 cost metric
template< typename TSource, typename TDest, typename TScoreValue, typename TScoreType, typename TStructuring, typename TCostModell, typename TSpec >
TScoreValue
_computeChain( TSource & source,
TDest & dest,
TCostModell cost,
Score< TScoreValue, TScoreType > const & score_,
TStructuring,
TSpec spec )
{
SEQAN_CHECK( !empty( source ) )
// define some basic types
typedef typename Value< TSource >::Type FragType;
typedef typename Weight< FragType >::Type WeightType;
typedef typename Key< FragType >::Type PositionType;
typedef typename Size< FragType >::Type SizeType;
typedef typename TSpec::Type SpecType;
SizeType dim = dimension( value( begin( source ) ) );
// construct containers for classes
String< MetaFragment_< FragType > > metas;
reserve( metas, length( source ) + 2 );
std::vector< WrapperPoint_< FragType > > points;
points.reserve( 2 * ( length( source ) + 2 ) );
//String< WrapperPoint_< FragType > > points;
//reserve( points, 2 * ( length( source ) + 2 ) );
String< ChainPoint_< FragType, SpecType > > end_points;
reserve( end_points, length( source ) + 2 );
// define origin and terminus fragment
FragType startingFrag( dim );
FragType endFrag( dim );
// build the environment (construct wrapper points, chain point, get coordinates of the terminus)
_buildChainEnvironment( source, metas, points, end_points, startingFrag, endFrag, spec );
typename Iterator< String< MetaFragment_< FragType > > >::Type lastMeta = end( metas );
goPrevious( lastMeta );
// set the score of the origin from -infinity to 0
setScore( value( begin( metas ) ), 0 );
// sort the wrapper points to apply the line sweep paradigma
std::sort( points.begin(), points.end(), ChainSorter_< WrapperPoint_< FragType > >( ) );
// build the RMT
RangeTree< ChainPoint_< FragType, SpecType >, SkipListStatic, RT< MaxTree< > >, TStructuring > tree( end_points, dim-1 );
// algorithm main loop
// traverse wrapper points
typename std::vector< WrapperPoint_< FragType > >::iterator pointIt = points.begin();
while( pointIt != points.end() )
{
// actual point is the beginning of a frag
// => search for preceding fragment
MetaFragment_< FragType > & meta = _meta(*pointIt );
if( !_isEnd( *pointIt ) )
{
ChainPoint_< FragType, SpecType > buffer( meta, dim - 1, true );
ChainPoint_< FragType, SpecType > * result = rangeMaxQuery( tree, buffer );
SEQAN_CHECK( result != NULL )
_setPred( meta, _meta( *result ) );
setScore( meta, _maxPriority( value( lastMeta ), meta, *result, cost, score_, dim ) );
}
else{
// point is the end of a frag
// => activate it
size_t offset = &meta - &_meta( *points.begin() );
ChainPoint_< FragType, SpecType > & point = end_points[ offset ];
setPriority( point, score( meta ) - _activatePriority( value( lastMeta ), point, cost, score_, dim ) );
activate( tree, point );
}
goNext( pointIt );
}
// perform backtracking
return _chainTrace( dest, metas );
}
}
#endif
|