1TOC 2 3Indices 4------- 5 6A substring index is a datatype which allows one to seek efficiently for all 7occurrences of a pattern in a string or a set of strings. Substring 8indices are very efficient for the exact string matching problem, i.e. 9finding all exact occurrences of a pattern in a text or a text 10collection. Instead of searching through the text in O(n) like 11online-search algorithms do, a substring index looks up the pattern in 12sublinear time o(n). Substring indices are full-text indices, i.e. they 13handle all substrings of a text in contrast to inverted files or 14signature files, which need word delimiters. SeqAn contains data 15structures to create, hold and use substring indices. Based on a unified 16concept, SeqAn offers the following concrete implementations defined as 17specializations of seqan:Class.Index: 18 19+-------------------------------------------------+-------------------------------------------------------------------------------------+ 20| **Specialization** | **Description** | 21+=================================================+=====================================================================================+ 22| seqan:Spec.IndexEsa | Abouelhoda et al., 2004]]) | 23+-------------------------------------------------+-------------------------------------------------------------------------------------+ 24| seqan:Spec.IndexWotd | Giegerich et al., 2003]]) | 25+-------------------------------------------------+-------------------------------------------------------------------------------------+ 26| seqan:Spec.IndexDfi | Weese, Schulz, 2008]]) | 27+-------------------------------------------------+-------------------------------------------------------------------------------------+ 28| seqan:Spec.IndexQGram | q-gram index | 29+-------------------------------------------------+-------------------------------------------------------------------------------------+ 30| [seqan:"Spec.Pizza & Chili Index" PizzaChili] | An adapter for the `Pizza & Chili <http://pizzachili.dcc.uchile.cl/>`__ index API | 31+-------------------------------------------------+-------------------------------------------------------------------------------------+ 32 33Suffix Tree Interface 34~~~~~~~~~~~~~~~~~~~~~ 35 36The unified concept allows the first three indices (seqan:Spec.IndexEsa, 37seqan:Spec.IndexWotd, seqan:Spec.IndexDfi) to be accessed just like a 38`suffix tree <Tutorial/Indices/SuffixTree>`__ independently of its 39concrete implementation. To access this (virtual) suffix tree SeqAn 40offers various [seqan:"Spec.VSTree Iterator" iterators]. 41 42Depth-First Search 43^^^^^^^^^^^^^^^^^^ 44 45In SeqAn a suffix tree (see definition 46`here <Tutorial/Indices/SuffixTree>`__) can be accessed with special 47suffix tree iterators, which differ in the way the tree nodes are 48traversed. For many sequence algorithms it is neccessary to do a full 49depth-first search (dfs) over all suffix tree nodes beginning either in 50the root (preorder dfs) or in a leaf node (postorder dfs). A preorder 51traversal (Fig.1) halts in a node when visiting it for the first time 52whereas a postorder traversal (Fig.2) halts when visiting a node for the 53last time. The following two figures give an example in which order the 54tree nodes are visited. 55 56+---------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ 57| `Image(source:trunk/docs/img/streePreorder.png, 300px) <Image(source:trunk/docs/img/streePreorder.png, 300px)>`__ | `Image(source:trunk/docs/img/streePostorder.png, 300px) <Image(source:trunk/docs/img/streePostorder.png, 300px)>`__ | 58+=====================================================================================================================+=======================================================================================================================+ 59| **Figure 1:** Preorder DFS | **Figure 2:** Postorder DFS | 60+---------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------------+ 61 62There are currently 2 iterators in SeqAn supporting a DFS search: 63 64+----------------------------------------+----------------+-----------------+ 65| **Iterator** | **Preorder** | **Postorder** | 66+========================================+================+=================+ 67| seqan:"Spec.BottomUp Iterator" | - | + | 68+----------------------------------------+----------------+-----------------+ 69| seqan:"Spec.TopDownHistory Iterator" | + | + | 70+----------------------------------------+----------------+-----------------+ 71 72If solely a postorder traversal is needed the seqan:"Spec.BottomUp 73Iterator" should be preferred as it is more memory efficient. Please 74note that the BottomUp Iterator is only applicable to 75seqan:Spec.IndexEsa indices. 76 77Example 78^^^^^^^ 79 80We want to construct the suffix tree of the string "abracadabra" and 81output the substrings represented by tree nodes in preorder dfs. All 82index related data structures are defined in ``seqan/index.h``, so we 83have to include this header (``seqan/sequence.h`` is included 84implicitly). 85.. includefrags:: demos/tutorial/index/index_preorder.cpp 86 :fragment: includes 87 88Next we create the string "abracadabra" and an index specialized with 89the type of this string. The string can be given to the index 90constructor. 91 92.. includefrags:: demos/tutorial/index/index_preorder.cpp 93 :fragment: initialization 94 95The seqan:Metafunction.Iterator metafunction expects two arguments, the 96type of the container to be iterated and a specialization tag, see the 97seqan:"Spec.VSTree Iterator" hierarchy. In this example we chose a 98seqan:"Spec.TopDownHistory Iterator" whose signature in the second 99template argument is ``TopDown< ParentLinks<Preorder> >``. Each suffix 100tree iterator constructor expects at least the index object and optional 101problem-dependent parameters. As all DFS suffix tree iterators implement 102the seqan:Concept.Iterator concept, they can be used via 103seqan:Function.goNext, seqan:Function.atEnd, etc. The string that 104represents the node the iterator points to is returned by 105seqan:Function.representative. 106.. includefrags:: demos/tutorial/index/index_preorder.cpp 107 :fragment: iteration 108 109Program output: 110 111:: 112 113 #html 114 <pre class="wiki" style="background-color:black;color:lightgray"> 115 116 a 117 abra 118 abracadabra 119 acadabra 120 adabra 121 bra 122 bracadabra 123 cadabra 124 dabra 125 ra 126 racadabra 127 128.. raw:: html 129 130 </pre> 131 132**Note:** A relaxed suffix tree (see 133`definition <Tutorial/Indices/SuffixTree>`__) is a suffix tree after 134removing the $ characters and empty edges. For some bottom-up algorithms 135it would be better not to remove empty edges and to have a one-to-one 136relationship between leaves and suffices. In that cases you can use the 137tags PreorderEmptyEdges or PostorderEmptyEdges instead of Preorder or 138Postorder or EmptyEdges for the TopDown Iterator. 139 140Assignments 141^^^^^^^^^^^ 142 143| *``Task`` 144``1``*\ `` :: Write a program that constructs an index of the seqan:Class.StringSet "tobeornottobe", "thebeeonthecomb", "beingjohnmalkovich" and outputs the strings corresponding to suffix tree nodes in postorder DFS.`` 145| *``Difficulty``*\ `` :: 2`` 146| *``Solution``*\ `` :: can be found ``\ ```here`` <Tutorial/Indices/Assignment1>`__ 147 148| *``Task`` 149``2``*\ `` :: Write a program that outputs all maximal unique matches (MUMs) between "CDFGHC" and "CDEFGAHC".`` 150| *``Difficulty``*\ `` :: 2`` 151| *``Solution``*\ `` :: can be found ``\ ```here`` <Tutorial/Indices/Assignment2>`__ 152 153Top-Down Iteration 154^^^^^^^^^^^^^^^^^^ 155 156For index based pattern search or algorithms traversing only the upper 157parts of the suffix tree the seqan:"Spec.TopDown Iterator" or 158seqan:"Spec.TopDownHistory Iterator" is the best solution. Both provide 159the functions seqan:Function.goDown and seqan:Function.goRight to go 160down to the first child node or go to the next sibling. The 161seqan:"Spec.TopDownHistory Iterator" additionally provides 162seqan:Function.goUp to go back to the parent node. The child nodes in 163seqan:Spec.IndexEsa indices are lexicographically sorted from first to 164last. For seqan:Spec.IndexWotd and seqan:Spec.IndexDfi indices this 165holds for all children except the first. 166 167Example 168^^^^^^^ 169 170In the next example we want to use the seqan:"Spec.TopDown Iterator" to 171efficiently search a text for exact matches of a pattern. We therefore 172want to use seqan:Function.goDown which has an overload to go down an 173edge beginning with a specific character. First we create an index of 174the text "How many wood would a woodchuck chuck." 175.. includefrags:: demos/tutorial/index/index_search.cpp 176 :fragment: initialization 177 178The main search can then be implemented as follows. The algorithm 179descends the suffix tree along edges beginning with the corresponding 180pattern character. In each step the unseen edge characters have to be 181verified. 182.. includefrags:: demos/tutorial/index/index_search.cpp 183 :fragment: iteration 184 185If all pattern characters could successfully be compared we end in the 186topmost node pattern is a prefix of. Thus, the suffixes represented by 187this node are the occurrences of our pattern. 188.. includefrags:: demos/tutorial/index/index_search.cpp 189 :fragment: output 190 191Program output: 192 193:: 194 195 #html 196 <pre class="wiki" style="background-color:black;color:lightgray"> 197 w 198 wo 199 wood 200 9 201 22 202 203.. raw:: html 204 205 </pre> 206 207Alternatively, we could have used seqan:Function.goDown to go down the 208path of a pattern instead single characters: 209.. includefrags:: demos/tutorial/index/index_search2.cpp 210 :fragment: output 211 212:: 213 214 #html 215 <pre class="wiki" style="background-color:black;color:lightgray"> 216 9 217 22 218 219.. raw:: html 220 221 </pre> 222 223Assignments 224^^^^^^^^^^^ 225 226| *``Task`` 227``3``*\ `` :: Write a program that iterates over all nodes of the suffix tree of the string "tobeornottobe" in preorder DFS. Use seqan:Function.goDown, seqan:Function.goRight and seqan:Function.goUp to iterate instead of seqan:Function.goNext or the operator++. Output the representatives.`` 228| *``Difficulty``*\ `` :: 4`` 229| *``Solution``*\ `` :: can be found ``\ ```here`` <Tutorial/Indices/Assignment3>`__ 230 231| *``Task`` 232``4``*\ `` :: Modify the program to efficiently skip nodes with representatives longer than 3. Move the whole program into a template function whose argument specifies the index type and call this function twice, once for the seqan:Spec.IndexEsa and once for the seqan:Spec.IndexWotd index.`` 233| *``Difficulty``*\ `` :: 5`` 234| *``Solution``*\ `` :: can be found ``\ ```here`` <Tutorial/Indices/Assignment4>`__ 235 236Access Suffix Tree Nodes 237^^^^^^^^^^^^^^^^^^^^^^^^ 238 239In the previous subsection we have seen how to walk through a suffix 240tree. We now want to know what can be done with a suffix tree iterator. 241As all iterators are specializations of the general VSTree Iterator 242class, they inherit all of its functions. There are various functions to 243access the node the iterator points at, so we concentrate on the most 244important ones. 245 246+-----------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------+ 247| **Function** | **Description** | 248+===================================================================================+==============================================================================================================================================+ 249| seqan:Function.representative | returns the substring that represents the current node, i.e. the concatenation of substrings on the path from the root to the current node | 250+-----------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------+ 251| seqan:Function.getOccurrence | returns a position where the representative occurs in the text | 252+-----------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------+ 253| seqan:Function.getOccurrences | returns a string of all positions where the representative occurs in the text | 254+-----------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------+ 255| seqan:Function.isRightTerminal | suffix tree]] figures) | 256+-----------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------+ 257| `isLeaf <http://www.seqan.de/dddoc/html_devel/FUNCTION_Index_23is_Leaf.html>`__ | tests if the current node is a tree leaf | 258+-----------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------+ 259| seqan:Function.parentEdgeLabel | returns the substring that represents the edge from the current node to its parent (only TopDownHistory Iterator) | 260+-----------------------------------------------------------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------+ 261 262**Note:** There is a difference between the functions isLeaf and 263isRightTerminal. In a relaxed suffix tree (see 264`definition <Tutorial/Indices/SuffixTree>`__) a leaf is always a suffix, 265but not vice versa, as there can be internal nodes a suffix ends in. For 266them isLeaf returns false and isRightTerminal returns true. 267 268Property Maps 269^^^^^^^^^^^^^ 270 271Some algorithms require to store auxiliary information (e.g. weights, 272scores) to the nodes of a suffix tree. To attain this goal SeqAn 273provides so-called property maps, simple Strings of a property type. 274Before storing a property value, these strings must first be resized 275with seqan:Function.resizeVertexMap. The property value can then be 276assigned or retrieved via seqan:Function.assignProperty or 277seqan:Function.getProperty, seqan:Function.property. It is recommended 278to call seqan:Function.resizeVertexMap prior to every call of 279seqan:Function.assignProperty to ensure that the property map has 280sufficient size. The following example iterates over all nodes in 281preorder dfs and recursively assigns the node depth to each node. First 282we create a seqan:Class.String of ``int`` to store the node depth for 283each suffix tree node. 284.. includefrags:: demos/tutorial/index/index_property_maps.cpp 285 :fragment: initialization 286The main loop iterates over all nodes in preorder DFS, i.e. parents are 287visited prior children. The node depth for the root node is 0 and for 288all other nodes it is the parent node depth increased by 1. The 289functions seqan:Function.assignProperty, seqan:Function.getProperty and 290seqan:Function.property must be called with a 291seqan:Metafunction.VertexDescriptor. The vertex descriptor of the 292iterator node is returned by seqan:Function.value and the descriptor of 293the parent node is returned by seqan:Function.nodeUp. 294.. includefrags:: demos/tutorial/index/index_property_maps.cpp 295 :fragment: iteration 296At the end we again iterate over all nodes and output the calculated 297node depth. 298.. includefrags:: demos/tutorial/index/index_property_maps.cpp 299 :fragment: output 300Program output: 301 302:: 303 304 #html 305 <pre class="wiki" style="background-color:black;color:lightgray"> 306 0 307 1 a 308 2 abra 309 3 abracadabra 310 2 acadabra 311 2 adabra 312 1 bra 313 2 bracadabra 314 1 cadabra 315 1 dabra 316 1 ra 317 2 racadabra 318 319.. raw:: html 320 321 </pre> 322 323*``Hint``*\ `` :: In SeqAn there is already a function seqan:Function.nodeDepth defined to return the node depth.`` 324 325Additional iterators 326^^^^^^^^^^^^^^^^^^^^ 327 328By now, we know the following iterators (n=text size, σ=alphabet size, 329d=tree depth): 330 331+----------------------------------------+------------------------------------------+-------------+---------------------+ 332| **Iterator specialization** | **Description** | **Space** | **Index tables** | 333+========================================+==========================================+=============+=====================+ 334| seqan:"Spec.BottomUp Iterator" | postorder dfs | O(d) | SA, LCP | 335+----------------------------------------+------------------------------------------+-------------+---------------------+ 336| seqan:"Spec.TopDown Iterator" | can go down and go right | O(1) | SA, Lcp, Childtab | 337+----------------------------------------+------------------------------------------+-------------+---------------------+ 338| seqan:"Spec.TopDownHistory Iterator" | can also go up, preorder/postorder dfs | O(d) | SA, Lcp, Childtab | 339+----------------------------------------+------------------------------------------+-------------+---------------------+ 340 341Besides the iterators described above, there are some 342application-specific iterators in SeqAn: 343 344+---------------------------------------------+-----------------------------------------------------------+-------------+--------------------------+ 345| **Iterator specialization** | **Description** | **Space** | **Index tables** | 346+=============================================+===========================================================+=============+==========================+ 347| seqan:"Spec.MaxRepeats Iterator" | maximal repeats | O(n) | SA, Lcp, Bwt | 348+---------------------------------------------+-----------------------------------------------------------+-------------+--------------------------+ 349| seqan:"Spec.SuperMaxRepeats Iterator" | supermaximal repeats | O(d+σ) | SA, Lcp, Childtab, Bwt | 350+---------------------------------------------+-----------------------------------------------------------+-------------+--------------------------+ 351| seqan:"Spec.SuperMaxRepeatsFast Iterator" | supermaximal repeats (optimized for enh. suffix arrays) | O(σ) | SA, Lcp, Bwt | 352+---------------------------------------------+-----------------------------------------------------------+-------------+--------------------------+ 353| seqan:"Spec.MUMs Iterator" | maximal unique matches | O(d) | SA, Lcp, Bwt | 354+---------------------------------------------+-----------------------------------------------------------+-------------+--------------------------+ 355| seqan:"Spec.MultiMEMs Iterator" | multiple maximal exact matches (w.i.p.) | O(n) | SA, Lcp, Bwt | 356+---------------------------------------------+-----------------------------------------------------------+-------------+--------------------------+ 357 358Given a string s a repeat is a substring r that occurs at 2 different 359positions i and j in s. The repeat can also be identified by the triple 360(i,j,\|r\|). A maximal repeat is a repeat that cannot be extended to the 361left or to the right, i.e. s[i-1]≠s[j-1] and s[i+\|r\|]≠s[j+\|r\|]. A 362supermaximal repeat r is a maximal repeat that is not part of another 363repeat. Given a set of strings s1, ..., sm a MultiMEM (multiple maximal 364exact match) is a substring r that occurs in each sequence si at least 365once and cannot be extended to the left or to the right. A MUM (maximal 366unique match) is a MultiMEM that occurs exactly once in each sequence. 367The following examples demonstrate the usage of these iterators: 368 369+---------------------------------------+ 370| **Example** | 371+=======================================+ 372| seqan:"Demo.Maximal Unique Matches" | 373+---------------------------------------+ 374| seqan:"Demo.Supermaximal Repeats" | 375+---------------------------------------+ 376| seqan:"Demo.Maximal Repeats" | 377+---------------------------------------+ 378 379q-gram Index 380~~~~~~~~~~~~ 381 382A q-gram index can be used to efficiently retrieve all occurrences of a 383certain q-gram in the text. It consists of various tables, called fibres 384(see `HowTo <HowTo/AccessIndexFibres>`__), to retrieve q-gram positions, 385q-gram counts, etc. However, it has no support for suffix tree 386iterators. A q-gram index must be specialized with a seqan:Class.Shape 387type. A seqan:Class.Shape defines q, the number of characters in a 388q-gram and possibly gaps between these characters. There are different 389specializations of seqan:Class.Shape available: 390 391+-----------------------------+--------------------+----------------------+ 392| **Specialization** | **Modifiable\*** | **Number of Gaps** | 393+=============================+====================+======================+ 394| seqan:Spec.UngappedShape | - | 0 | 395+-----------------------------+--------------------+----------------------+ 396| seqan:Spec.SimpleShape | + | 0 | 397+-----------------------------+--------------------+----------------------+ 398| seqan:Spec.OneGappedShape | + | 0/1 | 399+-----------------------------+--------------------+----------------------+ 400| seqan:Spec.GappedShape | - | any | 401+-----------------------------+--------------------+----------------------+ 402| seqan:Spec.GenericShape | + | any | 403+-----------------------------+--------------------+----------------------+ 404 405- - *fixed at compile time*, + *can be changed at runtime* 406 407Each shape evaluates a gapped or ungapped sequence of q characters to a 408hash value by the Functions seqan:Function.hash, 409seqan:Function.hashNext, etc. For example, the shape 1101 represents a 4103-gram with one gap of length 1. This shape overlayed with the 411seqan:Spec.Dna text "GATTACA" at the third position corresponds to 412"TT-C". The function seqan:Function.hash converts this 3-gram into 41361=((\ **3**\ \*4+\ **3**)\*4+\ **1**. 4 is the alphabet size in this 414example (see seqan:Metafunction.ValueSize). 415 416The q-gram index offers different function to search or count 417occurrences of q-grams in an indexed text, see 418seqan:Function.getOccurrences, seqan:Function.countOccurrences. A q-gram 419index over a seqan:Class.StringSet stores occurrence positions in the 420same way as the ESA index and in the same fibre (Fibre\_SA). If only the 421number of q-grams per sequence are needed the QGram\_Counts and 422QGram\_CountsDir fibres can be used. They store pairs 423``(seqNo, count)``, ``count``>0, for each q-gram that occurs ``counts`` 424times in sequence number ``seqNo``. 425 426To efficiently retrieve all occurrence positions or all pairs 427``(seqNo, count)`` for a given q-gram, these positions or pairs are 428stored in contiguous blocks (in QGram\_SA, QGram\_Counts fibres), called 429buckets. The begin position of bucket i is stored in directory fibres 430(QGram\_Dir, QGram\_CountsDir) at position i, the end position is the 431begin positions of the bucket i+1. The default implementation of the 432seqan:Spec.IndexQGram index maps q-gram hash values 1-to-1 to bucket 433numbers. For large q or large alphabets the seqan:Spec.OpenAddressing 434index can be more appropriate as its directories are additionally bound 435by the text length. This is realized by a non-trivial mapping from 436q-gram hashes to bucket numbers that requires an additional fibre 437(QGram\_BucketMap). 438 439For more details on q-gram index fibres see the 440`HowTo <HowTo/AccessIndexFibres>`__ or seqan:"Tag.QGram Index Fibres". 441 442Example 443^^^^^^^ 444 445We want to construct the q-gram index of the string "CATGATTACATA" and 446output the occurrences of the ungapped 3-gram "CAT". As 3 is fixed at 447compile-time and the shape has no gaps we can use a 448seqan:Spec.UngappedShape which is the first template argument of 449seqan:Spec.IndexQGram, the second template argument of 450seqan:Class.Index. Next we create the string "CATGATTACATA" and 451specialize the first index template argument with the type of this 452string. The string can be given to the index constructor. 453.. includefrags:: demos/tutorial/index/index_qgram.cpp 454 :fragment: initialization 455 456To get all occurrences of a q-gram, we first have to hash it with a 457shape of the same type as the index shape (we can even use the index 458shape returned by seqan:Function.indexShape). The hash value returned by 459seqan:Function.hash or seqan:Function.hashNext is also stored in the 460shape and is used by the function seqan:Function.getOccurrences to 461retrieve all occurrences of our 3-gram. 462.. includefrags:: demos/tutorial/index/index_qgram.cpp 463 :fragment: output 464 465Program output: 466 467:: 468 469 #html 470 <pre class="wiki" style="background-color:black;color:lightgray"> 471 0 472 8 473 474.. raw:: html 475 476 </pre> 477 478Assignments 479^^^^^^^^^^^ 480 481| *``Task`` 482``5``*\ `` :: Write a program that outputs all occurrences of the gapped q-gram "AT-A" in "CATGATTACATA".`` 483| *``Difficulty``*\ `` :: 3`` 484| *``Solution``*\ `` :: can be found ``\ ```here`` <Tutorial/Indices/Assignment5>`__ 485 486| *``Task`` 487``6``*\ `` :: Create and output a matrix M where M(i,j) is the number of common ungapped 5-grams between sequence i and sequence j for 3 random seqan:Spec.Dna sequences, each not longer than 200 characters. Optional: Run the matrix calculation twice, once for an seqan:Spec.IndexQGram and once for an seqan:Spec.OpenAddressing index and output the directory sizes (QGram_Dir, QGram_CountsDir fibre).`` 488| *``Difficulty``*\ `` :: 5`` 489| *``Hint``*\ `` :: A common g-gram that occurs a times in one and b times in the other sequence counts for min(a,b).`` 490| *``Solution``*\ `` :: can be found ``\ ```here`` <Tutorial/Indices/Assignment6>`__ 491 492Handling Multiple Sequences 493~~~~~~~~~~~~~~~~~~~~~~~~~~~ 494 495The previous sections briefly described how an index of a set of strings 496can be instantiated. Instead of creating an seqan:Class.Index of a 497seqan:Class.String you create one of a seqan:Class.StringSet. A 498character position of this string set can be one of the following: 499 500#. A local position (default), i.e. seqan:Class.Pair (seqNo, seqOfs) 501 where seqNo identifies the string within the stringset and the seqOfs 502 identifies the position within this string. 503 504``2. A global position, i.e. single integer value between 0 and the sum of string lengths minus 1 (global position). This integer is the position in the gapless concatenation of all strings in the seqan:Class.StringSet to a single string.`` 505``The meta-function seqan:Metafunction.SAValue determines, which position type (local or global) will be used for internal index tables (suffix array, q-gram array) and what type of position is returned by functions like seqan:Function.getOccurrence or seqan:Function.position of a seqan:Class.Finder. `` 506``seqan:Metafunction.SAValue returns a seqan:Class.Pair = local position by default, but could be specialized to return an integer type = global position for some applications.`` 507``If you want to write algorithms for both variants you should use the functions seqan:Function.posLocalize, seqan:Function.posGlobalize, seqan:Function.getSeqNo and seqan:Function.getSeqOffset.`` 508 509Submit a comment 510^^^^^^^^^^^^^^^^ 511 512If you found a mistake, or have suggestions about an improvement of this 513page press: 514[/newticket?component=Documentation&description=Tutorial+Enhancement+for+page+http://trac.seqan.de/wiki/Tutorial/Indices&type=enhancement 515submit your comment] 516 517.. raw:: mediawiki 518 519 {{TracNotice|{{PAGENAME}}}} 520